時間複雑

Question

こんにちは、私は、次の2つのコード断片上の私の分析に関するいくつかの疑問持つ分析に関する質問：

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++; 
    } 

ループがn/2回実行される一方、外側、及び内部whileループは1 + 2 + ... + n/2回実行されます。したがって、複雑さもO（n^2）ですか？

私は第2の問題についての私の分析についてはあまり確信していませんでした。

ありがとうございました！

Answer 1

あなたはそうです。正しい解決策は数​​えることです。

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

はO(log n)複雑性を有する。

なお：一方

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

は、O(n)複雑性を有します。