一個很簡單的歸簡法的Python實現。

今天直接切入主題吧。

歸簡法指的是將某一問題轉化成另外一個問題。我們通常都會傾向於將一個未知問題歸簡成一個已經解決的問題。

下面嘗試舉出一個簡單的例子。

假設我們想現在從某個數字列表中找出兩個彼此最接近但不相等的數。即兩者間的絕對差是最小的：

# 檢查兩個數字絕對值差最小nfrom random import randrangenseq = [randrange(10**10) for i in range(100)]ndd = float("inf")nfor x in seq:n for y in seq:n if x == y:n continuen d = abs(x-y)n if d < dd:n xx, yy, dd = x, y, dnnprint(str(xx) + ", " + str(yy))n

如果這樣做的話，會有兩層嵌套循環，他們各自都對seq進行了遍歷，這顯然是一個平方級的操作。這往往效率不會讓人滿意。

這是如果可以想到，處理一個已經排好序的序列相對來說會更容易一點，而排序通常是一個線性對數級或者Θ(nlgn)級的操作。因為你肯定知道已經排好序的序列中最接近的兩個數必然是相鄰的，於是你就可以這樣做:

# 先排序再查找nfrom random import randrangenseq = [randrange(10**10) for i in range(100)]nseq.sort()ndd = float("inf")nfor i in range(len(seq)-1):n x, y = seq[i], seq[i+1]n if x == y:n continuen d = abs(x-y)n if d < dd:n xx, yy, dd = x, y, dnnprint(str(xx) + ", " + str(yy))n

這樣子，演算法就會變得更快。

新的排序演算法是線性對數級的，由排序操作主導。

我們將找出一個序列中最快的兩個數的問題轉化為找出一個已經排序序列中最接近的兩個數。

這個只是一個簡單歸簡法的例子。在平時開發項目的過程中，一般都是要將答案轉化一下才能使用的。

今天就寫到這裡，謝謝各位關注。

西安這邊的天氣，已經慢慢轉冷，快到深秋了。

希望大家都健健康康的，早睡早起。

推薦閱讀：