O(n log log n) временная сложность

У меня есть короткая программа:

Given any n:
i = 0;
while (i < n) {
   k = 2;
   while (k < n) {
        sum += a[j] * b[k]
        k = k * k;
   }
   i++;
}

Асимптотическое время выполнения этого алгоритма равно O(n log log n). Почему это так? Я понимаю, что вся программа будет запускаться как минимум n раз. Но я не уверен, как найти журнал log n. Внутренний цикл зависит от k * k, поэтому очевидно, что он будет меньше n. И это было бы просто n log n, если бы каждый раз было k/2. Но как понять, что ответ будет log log n?


algorithm logarithm
person chrismanderson    schedule 05.03.2011    source источник
comment
Для более подробного объяснения ПОЧЕМУ здесь нужно найти вопрос: stackoverflow.com/questions/487258/   -  person Simon    schedule 05.03.2011

Ответы (3)


arrow_upward
8
arrow_downward

Для математического доказательства внутренний цикл можно записать так:

T(n) = T(sqrt(n)) + 1

w.l.o.g assume 2 ^ 2 ^ (t-1)<= n <= 2 ^ (2 ^ t)=>
we know  2^2^t = 2^2^(t-1) * 2^2^(t-1)
T(2^2^t) = T(2^2^(t-1)) + 1=T(2^2^(t-2)) + 2 =....= T(2^2^0) + t =>
T(2^2^(t-1)) <= T(n) <= T(2^2^t) = T(2^2^0) + log log 2^2^t = O(1) + loglogn

==> O(1) + (loglogn) - 1 <= T(n) <= O(1) + loglog(n) => T(n) = Teta(loglogn).

и тогда общее время равно O(n loglogn).

Почему внутренний цикл равен T(n)=T(sqrt(n)) +1? сначала посмотрите, когда внутренний цикл прерывается, когда k>n означает, что до этого k было не менее sqrt(n), или на двух уровнях до того, как было не более sqrt(n), поэтому время выполнения будет T(sqrt(n)) + 2 T(n) T(sqrt(n)) + 1.

person Saeed Amiri    schedule 05.03.2011
comment
@Tymek, я обновил ответ, надеюсь, это поможет, но будьте осторожны, внутренний цикл не равен sqrt (n) + 1, я доказал, что внутренний цикл равен log log n, я сказал, что во внутреннем цикле у нас есть T(n) = T(sqrt(n)) + 1. - person Saeed Amiri; 21.06.2012

arrow_upward
0
arrow_downward

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

Например: в вашем случае значение k следующее. Пусть i в скобках обозначает, сколько раз цикл был выполнен.

 2 (0) , 2^2 (1), 2^4 (2), 2^8 (3), 2^16(4), 2^32 (5) , 2^ 64 (6) ...... till n (k) is reached. 
The value of k here will be O(log log n) which is the number of times the loop has executed.

Ради предположений предположим, что n равно 2^64. Теперь log (2^64) = 64 и log 64 = log (2^6) = 6. Следовательно, ваша программа запускалась 6 раз, когда n равно 2^64.

person rombi    schedule 17.06.2017

arrow_upward
0
arrow_downward

Я думаю, что если коды такие, то должно быть n*log n;

i = 0;
while (i < n) {
    k = 2;
    while (k < n) {
        sum += a[j] * b[k]
        k *= c;// c is a constant bigger than 1 and less than k;
    }
i++;
}
person Yin Jin    schedule 19.09.2019