O (n log log n) сложность времени - PullRequest
Новая
       14

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

9 голосов
/ 05 марта 2011

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

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 раз.Но я не уверен, как найти журнал журнала n.Внутренний цикл зависит от k * k, поэтому он, очевидно, будет меньше n.И было бы просто n log n, если бы оно было k / 2 каждый раз.Но как бы вы поняли, что ответ будет log log n?

Ответы [ 2 ]

7 голосов
/ 05 марта 2011

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

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 & ge; T (n) & ge; T (sqrt (n)) + 1.

0 голосов
/ 17 июня 2017

Время Сложность цикла равна 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.

...