Временная сложность вложенного цикла while

Я не понимаю, как определить временную сложность цикла while в этом утверждении:

procedure P (integer n);
 for (i: 1 to n)
   x := n;
   while (x > 0)
         x := x - i;

Я знаю, что цикл for выполняется (n-1) раз. Сначала я думал, что цикл while будет выполняться n раз, потому что я принял i за 1, но это не так. Я ввожу числа, чтобы увидеть, когда программа остановится, но не вижу постоянного шаблона. Я заметил, что по мере увеличения n цикл while выполняется дольше (но ненамного), поэтому может ли это быть несколько логарифмическим? Заранее спасибо.


loops algorithm time-complexity big-o
person collegesista    schedule 18.10.2016    source источник

Ответы (2)


arrow_upward
5
arrow_downward

Первый запуск дает n циклов while
Второй запуск дает n/2 циклов while
Третий запуск производит n/3 циклов while
k-й запуск дает n/k циклов while

Таким образом, общее время пропорционально

n * (1/1 + 1/2 + 1/3 +...+1/n)

В скобках мы видим частичную сумму гармонического ряда, стремящуюся к натуральному логарифму n, а сложность O(n log n)

person MBo    schedule 18.10.2016

arrow_upward
0
arrow_downward

MBo ответ хорошо детализирован. Если вы зашли так далеко, возможно, вы спрашиваете себя, почему для первого запуска есть n циклов while, для второго запуска n/2 циклов while и т. д.

     x := n;
     while (x > 0)
         x := x - i;

Все циклы выполняются до x==0 по условию цикла while

поэтому первый запуск цикла while: n-t*1=0 раз для некоторого целого числа t и i==1

второй запуск цикла while: n-t*2=0 раз для некоторого целого числа t и i==1

Получаем для первого n=t для второго n=2tтак n/2=t для третьего n/3=t

person gbox    schedule 28.01.2020