Вычислительная стоимость

Question

Есть ли кто-нибудь, кто знает, какова вычислительная стоимость этих двух частей кода?

while (n > 2)
   n = sqrt(n);

while (n > 2)
   n = log(n);

Answer 1

Второй будет O(log* n), где log * - повторный логарифм .

Анализ первого выдает что-то вроде этого:

sqrt(n) = n ^ (1/2)
sqrt(sqrt(n)) = n ^ (1/4)
sqrt(sqrt(sqrt(n))) = n ^ (1/8)
...
sqrt applied k times = n ^ (1/2^k)

Учтите, что первый алгоритм выполняется k раз (в основном, сколько раз мы должны применить sqrt до n <= 2).

Подумайте над этим рассуждением:

n ^ (1/2^k) = p (p <= 2) | ^ (2^k)
n = p ^ (2^k) | log
log n = (2^k) log p | log
log log n = log (2 ^ k) + log log p
log log n = klog2 + log log p
=> k ~= log log n

Итак, первый алгоритм - O(log log n).

Answer 2

Ответ на первый должен стать очевидным, если его переписать в домене журнала:

n = log2(n);
while (n > 1)
    n = n / 2;

Сколько раз вам нужно вдвое сократить число, чтобы достичь 1?O (log n).