變量循環的時間複雜度

我想嘗試計算我的程序（在Python中）的O（n）。這裏有兩個問題：變量循環的時間複雜度

1：我有O（n）的非常基本知識[又名：我知道O（n）具有隨時間和計算做]

和

2：我的程序中的所有循環都沒有設置爲任何特定的值。它們基於輸入數據。

2010-01-15 calccrypto

這正是N表示在大哦符號（你叫什麼爲O（n））。 N代表輸入的大小。這取決於問題。也許你可以分享更多的上下文嗎？ – 2010-01-15 00:28:22

你的第二個「問題」不是問題，如果你解決了第一個問題，你會知道這個問題。我想你應該先做一些基本的學習，然後回來，如果你有更具體的問題。 – 2010-01-15 00:28:57

確實。如果沒有遞歸，並且所有循環的迭代次數不變，則時間複雜度爲O（1）。 – 2010-01-15 00:29:27

n in O(n)意味着正好是輸入大小。所以，如果我有這樣的代碼：

def findmax(l): 
    maybemax = 0 
    for i in l: 
     if i > maybemax: 
      maybemax = i 
    return maybemax

然後我會說，複雜性是O(n) - 需要多長時間是正比於輸入大小（因爲循環循環多次的l長度）。

如果我有

def allbigger(l, m): 
    for el in l: 
     for el2 in m: 
      if el < el2: 
       return False 
    return True

然後，在最壞的情況下（也就是，當我回到True），我有長len(l)的一個循環，並在它裏面，長度len(m)之一，所以我說，它是O(l * m)或O(n^2)如果列表預計大約相同的長度。

2010-01-15 00:31:53 pavpanchekha

你只需要知道函數調用在你的循環中需要多長時間並將它們分解。例如'for i in range（n）：if i in arr：do something'實際上是O（N^2）而不是O（N），因爲in運算符需要O（N）時間。 – JPvdMerwe 2010-01-21 13:02:20

嘗試了這一點，開始，然後前往維基：

2010-01-15 02:19:06

回答