Блог

Я озадачен тем, как определить временную сложность для цикла 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 выполняется дольше (но не намного), так может ли это быть несколько логарифмическим? Заранее спасибо.

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

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

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

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

Ответ 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