這些簡單循環的時間複雜度如何計算？

Question

我瞭解：

for (int i=0; i<n; i++) 

這個時間複雜度爲O(n)。

for (int i=0; i<n; i++) 
    for (int j=0; j<n; j++) 
     for (k=0; k<n; k++) 

這是O(n^3)對不對？

i=1 
do 
    //...... 
    i++ 
while (i*2 <n) 

是這樣的O(n)？或者它確切地說是O(n/2)？

Answer 1

O(n/2)是O(n)僅具有1/2的常數係數。係數可以是100億，它仍然是O(n)，而不是例如。 O(n^(1.0001))這是一個不同的複雜等級。

Answer 2

第一個O（n ），你是對的。

你的第二算法是爲O（n/2）=O（Cn）的 = 爲O（n）。 1/2是一個常量，所以我們可以安全地丟棄它。

Answer 3

第一個複雜度O（n^3），正確。 第二個，O（cn），c常數。不管c有多大，根據big-O的定義，複雜度仍然是O（n）。

但是，O符號被認爲是有害的。請參閱here。

Answer 4

的代碼將該片段：

i=1 
do 
    //...... 
    i++ 
while (i*2 < n); 

等同於一個：

for (i = 1; i < n/2 ; ++ i); 

從表面上看，這是O(n)。