運行時間使用大Θ符號

Question

def filter(f, lst):  
    if lst == []: return [] 
    if f(lst[0]): return [lst[0]] + filter(f, lst[1:]) 
    return filter(f, lst[1:]) 

def my_reverse(lst):  # Reverse the list 
    def reverse_helper(x,y): 
     if x == []: return y 
     return reverse_helper(x[1:], [x[0]] + y) 
    return reverse_helper(lst, []) 

def revfilter_alpha(f, lst): # Reverse and filter ... 
    return my_reverse(filter(f, lst)) 

def revfilter_beta(f, lst): # Reverse and filter ... 
    if lst == []: return [] 
    return revfilter_beta(f, lst[1:]) + ([lst[0]] if f(lst[0]) else []) 

有人可以向我解釋如何確定這些BigΘ表示法中的運行時間？我已經閱讀了很多東西，但仍然不知道從哪裏開始。

在filter中，我認爲它是Θ（n^2），因爲它用n個遞歸調用來檢查大小爲n的列表中的每個元素，並帶有n個遞歸調用，所以n * n。

revfilter_beta看起來非常相似，只是在過濾時反轉，所以這也不會是Θ（n^2）？

revfilter_alpha確實過濾然後反向，所以這不是n^2 * n^2 =Θ（n^4）？

有沒有人有任何想法？

Answer 1

filter有n遞歸調用，但是你也在每次迭代時做一個複製操作，這需要n，所以你最終得到Θ（n^2）。如果你實現了'正確'它應該是Θ（n）。

與my_reverse相同。

與revfilter_beta相同。

revfilter_alpha只是做了一個filter然後一個reverse，使得Θ（n^2 + n^2）=Θ（n^2）。

---

編輯：讓我們來看看filter多一點。

你想知道的是相對於輸入大小執行了多少操作。 O(n)表示在最壞的情況下，您將按照n的操作順序進行操作。我說「按順序」，因爲你可以，例如，做O(n/2)操作，或O(4n)，但最重要的因素是n。也就是說，隨着n增長，常數因子變得越來越不重要，所以我們只查看非常數因子（在這種情況下爲n）。

那麼，filter在n的大小列表上執行多少操作？

讓我們從下往上看。 n是0還是空列表？然後它會返回一個空列表。所以我們說這是1個操作。

如果n是1呢？它將檢查是否應該包含lst[0]--該檢查需要很長時間才能調用f - 然後它將複製列表的其餘部分，並對該副本執行遞歸調用，在這種情況下，這是一個空列表。所以filter(1)需要f + copy(0) + filter(0)操作，其中copy(n)是複製列表需要多長時間，並且f是檢查是否應該包含元素需要多長時間，假定每個元素需要相同的時間量。

filter(2)怎麼樣？它將執行1次檢查，然後複製剩餘的清單，並在餘下部分撥打filter：f + copy(1) + filter(1)。

您可以看到圖案。filter(n)需要1 + copy(n-1) + filter(n-1)。現在

，copy(n)只是n - 它需要n操作切片以這種方式列表。所以我們可以進一步簡化：filter(n) = f + n-1 + filter(n-1)。

現在，你可以嘗試只擴大了filter(n-1)幾次，看看會發生什麼：

filter(n) = f + n-1 + filter(n-1) 
      = 1 + n-1 + (f + n-2 + filter(n-2)) 
      = f + n-1 + f + n-2 + filter(n-2) 
      = 2f + 2n-3 + filter(n-2) 
      = 2f + 2n-3 + (f + n-3 + filter(n-3)) 
      = 3f + 3n-6 + filter(n-3) 
      = 3f + 3n-6 + (f + n-4 + filter(n-4)) 
      = 4f + 4n-10 + filter(n-4) 
      = 5f + 5n-15 + filter(n-5) 
      ... 

我們可以概括爲x重複？這1, 3, 6, 10, 15 ...序列是三角形的數字 - 即1，1+2，1+2+3，1+2+3+4等所有號碼從1到x是x*(x-1)/2總和。

  = x*f + x*n - x*(x-1)/2 + filter(n-x) 

現在，什麼是x？我們會有多少次重複？那麼，你可以看到，當x = n，你沒有更多的遞歸 - filter(n-n) = filter(0) = 1。因此，我們的公式現在是：

filter(n) = n*f + n*n - n*(n-1)/2 + 1 

，我們可以進一步簡化：

filter(n) = n*f + n^2 - (n^2 - n)/2 + 1 
      = n*f + n^2 - n^2/2 + n/2 + 1 
      = n^2 - n^2/2 + f*n + n/2 + 1 
      = (1/2)n^2 + (f + 1/2)n + 1 

因此，有雅有它 - 一個相當詳細的分析。那將是Θ((1/2)n^2 + (f + 1/2)n + 1) ...假設f是不重要的（說f = 1），得到Θ((1/2)n^2 + (3/2)n + 1)。

現在你會發現，如果copy(n)了一定量的時間，而不是時間的線性量（如果copy(n)爲1，而不是n），那麼你就不會得到在那裏n^2項。

我承認，當我最初說Θ(n^2)時，我並沒有在我的腦海裏這麼做。相反，我想：好的，你有n遞歸步驟，並且由於copy，每個步驟將花費n時間量。 n*n = n^2，因此Θ(n^2)。要做到這一點有點更確切地說，n縮小在每一步，讓您真正擁有n + (n-1) + (n-2) + (n-3) + ... + 1，這最終是相同的圖如上：n*n - (1 + 2 + 3 + ... + n) = n*n - n*(n-1)/2 = (1/2)n^2 + (1/2)n，這是相同的，如果我用過的0代替f，上述。同樣，如果您有n步驟，但每個步驟都需要1而不是n（如果您不需要複製該列表），那麼您將擁有1 + 1 + 1 + ... + 1,n次或簡單地n。

但是，這需要更多的直覺，所以我想我還會告訴你可以應用於任何事情的蠻力方法。

Answer 2

您所有的功能都是O(N^2)，因爲它們每遞歸一步需要O(N)時間，並且在長度爲N的列表上將會有N步驟。

在您的函數中有兩個昂貴的操作（即O(N)）。第一個是切片（例如lst[1:]）。第二個是列表級聯（使用+運算符）。

這兩者可能比您期望的要貴，主要是因爲Python的列表不像其他語言中的列表數據類型。在引擎蓋下他們是數組，而不是鏈表。可以在O（1）時間的鏈接列表上執行上述操作（儘管O(1)切片具有破壞性）。例如，在Lisp中，您使用的算法將是O(N)，而不是O(N^2)。

因爲沒有tail call elimination，遞歸在Python中通常也不是最優的。在最近的版本中，Python的默認遞歸限制爲1000，所以很長的列表將打破純粹的遞歸解決方案，除非您在sys模塊中混亂以增加限制。

也可以在Python中使用這些算法的O(N)版本，但是您希望儘可能避免使用上面昂貴的列表操作。我建議使用生成器，而不是遞歸，這是一種更「pythonic」風格的編程。

使用發生器進行過濾非常容易。內置filter函數做它了，但你可以在短短的幾行寫自己：

def my_filter(f, iterable): 
    for e in iterable: 
     if f(e): 
      yield e 

逆轉事物的秩序是有點複雜，因爲你需要或者能夠做到隨機訪問源代碼或使用額外的空間（即使列表遵循序列協議並且可以隨機訪問，您的算法會使用該空間的堆棧）。內置reversed功能僅適用於序列，但這裏是在可迭代的（如另一個發電機）的作品版本：

def my_reversed(iterable): 
    storage = list(iterable) # consumes all the input! 
    for i in range(len(storage)-1, -1, -1): 
     yield storage[i] 

注意，不像許多發電機組，這在消耗它的所有輸入一次前它開始產出產量。不要在無限的輸入上運行它！

您可以按任意順序撰寫這些文章，my_reversed(filter(f, lst))應該等同於filter(f, my_reversed(lst))（儘管對於後者，使用內置的reversed函數可能會更好）。

上述兩個發電機（以及它們的任一順序組成）的運行時間將爲O(N)。