Итерационная функция

Question

Застрял со мной HW - Нужно попробовать сложность

time=0;
for (i=n; i>=1; i = sqrt(i))
 for (j=1; j<=i; j++)
 time++;

Что я сделал - Первый цикл идет так: i = n, n ^ (1/2), n ^ (1/4)... 1, чем мы получаем:

n ^ (1/2) ^ k = 1, если я регистрирую обе стороны, одна сторона получает 0 ... что мне делать?

Answer 1

Я предполагаю, что где-то есть опечатка, потому что в противном случае это & ​​Theta; (∞), если вход n не меньше 1. (Для i == 1, обновление i = sqrt(i) не изменится i, поэтому это бесконечный цикл.)

Итак, давайте предположим, что это на самом деле

time = 0;
for (i = n; i > 1; i = sqrt(i))
    for (j = 1; j <= i; j++)
        time++;

Затем, чтобы получить сложность вложенных циклов, необходимо суммировать сложность внутреннего цикла для каждой итерации внешнего цикла. Здесь, очевидно, внутренний цикл выполняется i раз, поэтому нам нужно суммировать значения, которые i проходит во внешнем цикле. Эти значения n, n^0.5, n^0.25, ..., n^(1/2^k), где k характеризуется

n^(1/2^(k+1)) < 2 <= n^(1/2^k)

или, что эквивалентно,

2^(2^k) <= n < 2^(2^(k+1))
2^k <= lg n < 2^(k+1)
k <= lg (lg n) < k+1
k = floor(lg(lg n))

Теперь осталось оценить сумму сверху и снизу, чтобы получить & Theta; алгоритма. Эта оценка очень проста, если вы начнете записывать суммы для нескольких (больших) значений n.