O符號環路

for(int i = 0; i < n; i++) { 
    for(int j = 0; j < i; j++) { 
     O(1); 
    } 
}

這裏的FUNC爲n * (n+1)/2但如果outerloop條件是i < log(n)什麼？我有問題與循環相互關聯。O符號環路

2017-06-21 thomas

如果將'n'替換爲別的，只要用'n *（n + 1）/ 2'替換同樣的東西中的每個'n'。這似乎歸結爲對基本代數缺乏瞭解（或暫時的精神錯亂）。 – Dukeling

你一定要算的迭代總數：

1 + 2 + 3 + .. + n - 1 = n * (n - 1)/2

爲你正確地推斷。當您將n替換爲log(n)時，只需在最終公式中執行相同操作即可，該公式爲log(n) * (log(n)+1)/2或Big-O表示法O((log(n))^2)。

2017-06-21 14:50:14

'1 + 2 + 3 + .. + n = n *（n + 1）/ 2'，而不是「1 + 2 + 3 + .. + n-1」。 –

@AnthonyLabarre當然，非常愚蠢的錯誤。 TNX。 –

如果外循環的條件變更爲i < log(n)然後嵌套雙迴路的總體複雜性構造的變化從爲O（n ）至O（的log（n））

您可以用簡單替換k = log(n)來顯示此值，因爲循環的複雜度爲k爲O（k ）。反轉取代產生O（log（n））。

2017-06-21 14:50:27 dasblinkenlight

對於嵌套for循環（當使用O符號，ofc時），您可以乘以所有這些的最壞情況。如果第一個循環轉到x並且有一個嵌套循環轉到i（我處於最壞情況x），那麼您的運行時複雜度爲O（x^2）

2017-06-21 15:18:01

回答