Анализ сложности времени алгоритма

Question

Привет Я пытаюсь проанализировать временную сложность этого алгоритма, но мне сложно разобрать и подсчитать, сколько раз будет выполняться заключительный цикл. Я понимаю, что первый цикл - log (n), но после этого я не могу получить сумму, которая хорошо оценивается. Вот алгоритм:

for(int i = 1; i <= n; i = 2*i){ 
    for(int j = 1; j <= i; j = 2*j){ 
     for(int k = 0; k <= j; k++){ 
      // Some elementary operation here. 
     } 
    } 
} 

Я не могу понять, сколько раз цикл к выполняет в общем w.r.t к п

Спасибо за любую помощь!

Answer 1

Это O (n).

1 + 2 + 4 + ... + 2^N == 2^(N + 1) - 1.

В последний цикл, для конкретного J, выполняет J раз.

И для конкретного i внутренние 2 цикла выполняют 1 + 2 + 4 + ... + i раз, что равно примерно 2 * i.

Таким образом, общее время выполнения составляет 1 * 2 + 2 * 2 + 4 * 2 + ... + N * 2, что составляет около 4 * Н.