Найти временную сложность алгоритма?

Question

Я думаю, что это бревно (LOGN), поскольку цикл повторяется журнал (LogN) раз ...

j=1; 
i=2; 
while (i <= n) do { 
    B[j] = A[i]; 
    j = j + 1; 
    i = i * i; 
} 

Answer 1

Вы правы, это O(lg(lg n)) где lg обозначает основание 2 логарифм.

Причина, заключающаяся в том, что последовательность значений i подчиняется правилу i = prev(i) * prev(i), которое оказывается для 2, 2, 2, 2, 4, 2, 8, ... для этапов 1, 2, 3 , 4, .... Иными словами, значение i после k итераций - 2^{2^k}.

Таким образом, цикл прекратится, как только 2^{2^k} > n или k > lg(lg(n)) (Просто lg два раза в обе стороны неравенства. Неравенство остается в силе, поскольку lg является возрастающей функцией.)