問題的分析時間複雜度

Question

您好我對我的分析基於以下兩個代碼片段有些疑惑：

1）

for (i = 1; i <= 1.5n; i++) 
     for (j = n; j >= 2; j--) 
      cout << i, j; 

外環將被執行1.5N倍，內環將執行n-2次。因此，複雜度爲O（1.5N *（N-2）= O（N^2）？

2）

j = 1; 
    while (j < n/2) { 
     i = 1; 
     while (i < j) { 
      cout << j << i; 
      i++; 
     } 
     j++; 
    } 

while循環將爲n執行/ 2倍外，和inner while循環將執行1 + 2 + ... + n/2次。因此，複雜性也是O（n^2）？

我不太確定我對第二個問題的分析。

非常感謝您的幫助！

Answer 1

你說得對。正確的解決方案是數數。

需要注意的是：

j = 0; 
while (j < n/2) { 
    j++; 
} 

有O(n)的複雜性，而：

j = 1; 
while (j < n) { 
    j *= 2; 
} 

有O(log n)複雜性。