Понимание временной сложности рядов геометрической прогрессии
По словам моего профессора, временная сложность следующего кода равна O(N), но я не понимаю, почему временная сложность такая.
int sum = 0;
for (int i=1; i<n; i=i*3) {
for (int j=1; j<=i; j++) {
sum++;
}
}
Насколько я понимаю, внешний цикл — это O(logN), а внутренний — O(i*N).
Так разве не должна быть временная сложность O(i*N) * O(logN) = NlogN?
Ответы 3
Поскольку вы двигаетесь, умножая на три, я бы выбрал следующий подход:
Попробуйте использовать значения n=729 (3^6), n=6561 (3^8), n=59049 (3^10) и n=531441 (3^12) и поставьте writeln("something"); рядом с командой sum++.
Подсчитайте, сколько раз что-то написано на вашем экране.
Если сложность O(N), эта сумма каждый раз будет умножаться на 9. Если сложность O(N log(N)), коэффициент будет выше.
В вашем коде внешний цикл выполняется примерно (log n) раз, потому что каждый раз я умножается на 3. Для каждого из этих запусков внутренний цикл выполняется i раз, причем с каждым циклом i становится больше.
Если сложить всю работу, проделанную внутренним циклом по всем итерациям внешнего цикла, получится нечто, пропорциональное n. Итак, ваш профессор прав: общая временная сложность вашего кода действительно равна O (n).
Внутренний цикл выполнит следующее количество итераций:
1 для первой внешней итерации
3 для второй внешней итерации
9 для 3-й внешней итерации
...
~n для последней внешней итерации.
Т.е. внутренний цикл полностью выполнится 1+3+9+ ... + ~n раз.
Это геометрическая прогрессия с элементами O(logn), а сумма ее равна O(n).
Это связано с тем, что гемеральная сумма геометрической прогрессии, начинающейся с a1, с отношением r и элементами x, равна:
Sx = a1 * (1 - r^x) / (1 - r)
Если вы используете 1 для a1, 3 для r и log для x, вы получите:
Slogn = 1 * (1 - 3^logn) / (1 - 3)
А поскольку 3^logn равно O(n), все выражение равно O(n).