Временная сложность вложенных в то время как петля

Question

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

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

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

Answer 1

Первый запуск делает п в то время-циклов
Второй пробег составляет п/2, а-циклы
Третьего пробега составляет п/3, а-циклов
к-я пробега составляет п/к в то время как циклы

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

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

в скобках мы можем увидеть частичную сумму harmonic series, которая стремится к натуральному логарифму п, и сложность о (п § п)