Вычислить сложность вложенного цикла for

Внешний цикл проходит через 1, 2, 4, 8, ... n, что занимает O(lg n) шагов, потому что вы можете удвоить только один O(lg < em>n) раз, пока не нажмете n.

Внутренний цикл делает то же самое. Он достигает только i, но на последней итерации внешнего цикла i достигает своего максимального значения, которое снова равно n, так что это также O(lg n).

В результате получается верхняя граница O((lg n)²), которая обычно обозначается аббревиатурой O(lg² n).

Как получить ответ самостоятельно

Подставьте в уравнение разные значения n и нарисуйте диаграмму, сколько раз выполняется самая внутренняя часть цикла:

s = 0;
for(i=1; i<=n; i*=2)
  for(j=1; j<=i; j*=2)
    s++;

Что-то вроде этого:

n     num_times_inner_loop_part_runs
1     1
2     3
3     3
4     6
5     6
6     6
7     6
8     10
9     10
...
15    10
16    15
...
31    15
32    21

Вы можете получить эти точки данных с помощью такой программы:

int n = 9;  //change this n
int counter = 0;
for(i=1; i<=n; i*=2){
  for(j=1; j<=i; j*=2){
    s++;
    counter++;
  }
}
cout << "counter is: " <<  counter << endl;

Нанесите num_times_inner_loop_part на координатную плоскость X/Y, и вы увидите кривую.

Назовите кривую, которая подходит ближе всего. В данном случае это X = (log(Y)^2)

Если вы нанесете свои данные и X = (log(Y)^2), вы обнаружите, что они должны перекрывать друг друга.

Таким образом, сложность этой функции составляет O((log(n))^2), что является улучшением по сравнению с O(n).

Анализ времени этого фрагмента кода:

Временная сложность вашего алгоритма может быть формально представлена ​​следующим образом:

Этот документ (последний слайд) может оказаться для вас чрезвычайно полезным .