Временная сложность вложенных петель

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 раз, а последний внутренний рамочную инф, если заявление вы выполнить один раз (если 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 раз для самого внутреннего цикла во время выполнения второго самого внутреннего цикла, а затем умножить его на общее время seondmost внутренний цикл выполнен