時間複雜度

Question

考慮以下代碼：

def count_7(lst): 
    if len(lst) == 1: 
     if lst[0] == 7: 
      return 1 
     else: 
      return 0 

    return count_7(lst[:len(lst)//2]) + count_7(lst[len(lst)//2:]) 

注：限幅操作將被視爲O（1）。

所以，我的演示告訴我這是O（n * logn），但我正在努力證明它科學。
樂意爲您服務！

Answer 1

好，數學（在某種程度上）我得到這樣的：

T(n) = 2T(n/2) + c 
T(1) = 1 

歸納公式：

T(n) = 2^k * T(n/2^k) + (2^k - 1) * c 
T(1) = 1 

n/2^k == 1時k == logN這樣：

T(n) = 2^logN * T(1) + (2^logN - 1) * c 

因爲T(1) = 1並應用對數性質

T(n) = n * 1 + (n-1) * c 
T(n) = n + n * c 
T(n) = n * (1+c) 
T(n) = O(n) 

一個線索，這不是O(n*logn)是你不必把兩個子問題結合起來。與mergesort不同，您必須將兩個子數組組合在一起，此算法不必對遞歸結果做任何處理，因此其時間可表示爲常量c。

更新：背後

該算法直覺應該是爲O（n），因爲您訪問的每個元素的數組中只有一次。這似乎並不重要，因爲遞歸永遠不會。

例如，您將問題分爲兩個子問題的一半大小，然後每個子問題也會被分成一半大小，並且會一直繼續下去，直到每個子問題的大小爲1. 完成後，您將擁有大小爲1的子問題，即n*O(1) = O(n)。

從第一個問題開始到第一個問題的大小爲1的對數爲對數，因爲在每一步中你都細分爲兩個。但是在每一步中，您對結果都不做任何處理，因此這不會增加解決方案的時間複雜性。

希望這有助於

Answer 2

最簡單的方法是假設n爲2簡單的多：n = 2m

你的算法的時間複雜度爲（c爲常數）：

t(n) = 2 t(n/2) + c 

而且使用遞歸你：

t(n) = 22 t(n/22) + 2c + c

     ...

     = 2log(n) t(n/2log(n)) + c(2log(n)-1 + ... + 22 + 21 + 20)

哪位可以通過注意到log(n) = m被簡化，並且因此2log(n) = 2m = n。

     = n + c(2log(n)-1 + ... + 22 + 21 + 20)

最後，和上面可以降低到2log(n)（相當於n）

t(n) = (1 + c) n 

所以您的解決方案是O（n）

Answer 3

您掃描的所有元素列出一次，那就是O（n）。簡單的遞歸掃描 的唯一區別就是掃描它們的順序。你做1，n/2，2，3/4n等等，而不是1,2,3 ......但複雜性是一樣的。