嵌套循環的時間複雜度

Question

for(int i = 1; i < n; i = i ∗ 2){ 
    for(int j = 0; j < n; j++){ 
     if(i == j){ 
      for(int k = 0; k < n; k++){ 
       // Do something elementary 
      } 
     }else{ 
      // Do another elementary thing 
     } 
    } 
} 

我正在做一些練習，有人可以幫我弄清楚上述算法的Θ嗎？我明白，如果它只是兩個外部嵌套循環，則時間複雜度應該是Θ（nlogn）。但我不知道如何處理if-else語句。提前謝謝了！

Answer 1

您執行外環log(n)次，因爲你我每一次雙重價值

然後你執行內環n次，最後內環INF if語句，你執行一次（如果i == j持有）n次，這整個內循環每次需要n + n步。

這給你一個上限的O(2n log(n))而且由於常量不改變漸進複雜的運行是由O(n log(n))

for(int i = 1; i < n; i = i ∗ 2){     ---------- 
for(int j = 0; j < n; j++){   ----------    | 
    if(i == j){         |   | 
     for(int k = 0; k < n; k++){  ----  |   | 
      // Do something elementary  | (n | + n)  | * log(n) 
     }        ----  |   | 
    }else{          |   | 
     // Do another elementary thing   |   | 
    }         ----------    | 
}                | 
}                | 
                ------------ 

注意，最內層循環每秒最內環只執行一次（有界！），並且由於第二個最內部的循環得到執行log n次（具有n步驟），我們必須將最內部循環的n時間添加到第二個最內部循環的運行時間，然後將它乘以最接近的最後循環的總時間內循環執行