Python的複雜性（運行時間）

Question

def f2(L): 
    sum = 0 
    i = 1 
    while i < len(L): 
     sum = sum + L[i] 
     i = i * 2 
    return sum 

設n是傳遞給該函數的列表L的大小。以下哪項最準確地描述了該函數的運行時間如何隨着n的增長而增長？

（一）它呈線性增長，如N一樣。 （b）它像n^2那樣以二次方式增長。

（c）增長小於線性。 （d）它的增長高於二次方。

我不明白你怎麼找出功能的運行時間和n的增長之間的關係。有人可以向我解釋這個嗎？

Answer 1

確定，因爲這是家庭作業：

這是代碼：

def f2(L): 
    sum = 0 
    i = 1 
    while i < len(L): 
     sum = sum + L[i] 
     i = i * 2 
    return sum 

這顯然是依賴於LEN（L）。

所以讓我們看看每一行，它的成本：

sum = 0 
i = 1 
# [...] 
return sum 

那些有明顯固定的時間，L. 的獨立的在循環中，我們有：

sum = sum + L[i] # time to lookup L[i] (`timelookup(L)`) plus time to add to the sum (obviously constant time) 
    i = i * 2 # obviously constant time 

多少次循環是否執行？ 它obvously依賴於L. 的大小允許呼叫loops(L)

所以我們得到的

loops(L) * (timelookup(L) + const)

的整體複雜身爲好人的我，我會告訴你該列表查找在蟒蛇恆定的，所以把它歸結爲

O(loops(L))（忽略常數因子，如大O約定暗示）

你的循環次數是多少次，基於的L？ （a）與列表中的項目一樣，列表中的項目（b）的數量與列表中的項目數量一樣多（？）。

（c）由於列表中的項目（d）比（b）更頻繁，因此次數更少？

Answer 2

我不是計算機專業的，我不要求有這種理論的強抓，但我想這可能是相關的人從我的角度，試圖促成一個答案。

你的函數總是需要時間來執行，如果它是在不同長度的list參數運行，那麼所花費的時間來運行該功能會相對多少元素在該列表中。

讓我們假設處理一個長度爲== 1的列表需要1個單位的時間。問題的問題是列表的大小與此函數執行時間的增加之間的關係變大。

此鏈接打破了大O記法的一些基本知識：http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

如果是O（1）複雜性（這是不是真正的你的AD選項之一），那麼這將意味着複雜性永不不管大小L.顯然在你的例子中，它正在做一個while循環，依賴於增長一個與L的長度相關的計數器i。我將集中討論i正在倍增的事實，以指示它將花費多長時間通過while循環和L的長度。基本上，試着比較while循環需要在len（L）的各個值上執行多少個循環，然後這將決定你的複雜性。 1個單位的時間可以通過while循環迭代1次。

希望我做出某種形式的貢獻在這裏，就這個問題我自己的專業知識的缺乏。

更新
澄清基於從ch3ka的評論，如果你做的比你現在有你的with循環中更多的，那麼你也將不得不考慮每個循環增加了複雜性。但是，因爲你的list lookup L[i] is constant complexity，跟隨它的數學，我們可以忽略這些複雜性。

Answer 3

這裏找出一個快速和骯髒的方式：

import matplotlib.pyplot as plt 

def f2(L): 
    sum = 0 
    i = 1 
    times = 0 
    while i < len(L): 
     sum = sum + L[i] 
     i = i * 2 
     times += 1 # track how many times the loop gets called 
    return times 

def main(): 
    i = range(1200) 
    f_i = [f2([1]*n) for n in i] 
    plt.plot(i, f_i) 

if __name__=="__main__": 
    main() 

...這會導致

橫軸爲L的大小，縱軸是多少乘以函數循環;大O應該是非常明顯的。

Answer 4

它O(log(len(L)))，如列表查找是一個常數時間的操作，該列表的大小無關。

Answer 5

當您查看該函數時，您必須確定列表大小將如何影響將發生的循環數。

在您的具體情況中，讓n增加並查看while循環將運行多少次。

n = 0, loop = 0 times 
n = 1, loop = 1 time 
n = 2, loop = 1 time 
n = 3, loop = 2 times 
n = 4, loop = 2 times 

查看模式？現在回答你的問題，不是：

(a) It grows linearly, like n does. (b) It grows quadratically, like n^2 does. 

(c) It grows less than linearly. (d) It grows more than quadratically. 

結帳Hugh的答案實證結果:)

Answer 6

考慮與長度的輸入N = 10會發生什麼。現在考慮如果輸入大小增加到20倍會發生什麼情況。運行時也會增加兩倍嗎？然後它是線性的。如果運行時間增長了4倍，那麼它是二次的。等