TIme сложность различных вложенных циклов

Question

Время Сложность цикла рассматривается как O (Logn), если переменные цикла делятся/умножаются на постоянную величину.

петля 1 ----

for (int i = 1; i <=n; i *= c) 
{ 
    // some O(1) expressions 
} 

петля 2 -----

for (int i = n; i > 0; i /= c) 
{ 
    // some O(1) expressions 
} 

Время Сложность цикла рассматривается как O (LogLogn), если переменные цикла уменьшается/увеличивалась экспоненциально на постоянную величину.

Here c is a constant greater than 1 

петля 3 ----

for (int i = 2; i <=n; i = pow(i, c)) 
{ 
    // some O(1) expressions 
} 

петля 4 -----

////Here fun is sqrt or cuberoot or any other constant root 
for (int i = n; i > 0; i = fun(i)) 
{ 
    // some O(1) expressions 
} 

Может кто-нибудь мне объяснить, почему это с учетом того, сколько раз внутренний цикл выполняется в этих циклах?

Если c = 1 в цикле 1 и петле 2, то он будет работать бесконечно, но он задан как логарифмическое время, почему?

как это O (loglogN) в петле 3 и петле 4?

Answer 1

Если c = 1 в цикле 1 и цикле 2, то он будет работать бесконечно, но он задан как логарифмическое время, почему?

Да вы правы, если c = 1 тогда мы получим бесконечные циклы, как для случая 1 и случая 2, поэтому условие «c является [п целое] константа больше 1» также необходимо для обоих case 1 и case 2, чтобы получить сложность O(log n).

---

Для случая 1, отметим, что i принимает значения 1, c, c2, c3, ..., clogc(n), так что есть в общей сложности log(n) много итераций, и для каждой итерации есть постоянный объем работы, чтобы сделать (т.е. O(1) объем работы), так общая сумма выполненных работ составляет log(n) * O(1) = O(log(n)).

Аналогично для случая 2, i принимает значения n, n/c, n/c2, n/c3, ..., , n/clogc(n), так что есть в общей сложности log(n) многих итераций и каждая итерация занимает постоянное количество времени, так что общее время сложность O(log(n)).

Для случая 3, i принимает значения 2, 2c, (2c)c = 2c2, (2c2)c = 2c3, ..., 2clogc(log(n)). Последний термин должен быть меньше или равен n, и у нас есть 2clogc(log(n)) = 2log(n) = n, что оправдывает стоимость нашего последнего срока. Таким образом, в общей сложности logc(log(n)) много итераций, и каждый занимает постоянное количество времени для запуска, поэтому общая временная сложность составляет O(log(log(n))).

Аналогично для случая 4, i принимает значения n, n1/c, (n1/c)1/c = n1/c2, n1/c3, ..., n1/clogc(log(n)), так что есть в общей сложности logc(log(n)) итераций и каждая итерация занимает много времени O(1), так что общая сложность времени O(log(log(n))).