О сложности времени алгоритма

Question

Что такое сложность времени проблемы ниже.

int j=1; 
while(j<n){ 
    j+=log(j+5); 
} 

Answer 1

Расширяя первые три члена суммы:

Вы можете видеть, что это просто сумма итераций log(log(j)) «с. Так как O (j) >> O (log (j)), то O (log (j)) >> O (log (log (j)), поэтому первый член затмевает все остальные члены.

поэтому

сумма составляет O (журнал (к)), что означает, что время сложность

.

Численные тесты показывают, что это на самом деле O (п^0,82 ...).

Answer 2

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

Легко показать, что цикл занимает по меньшей мере п/журнал (п + 5) = п/(лог п × лог 5) итераций, чтобы закончить, так как он рассчитывает до n, и каждая итерация увеличивает счетчик на сумму, строго меньшую, чем log (n +5). Таким образом, асимптотическая временная сложность составляет не менее Ω (n/log n).

Показано, что это также O (п/войти п), и, таким образом, Θ (п/войти п), кажется немного сложнее. В основном, мой аргумент в том, что при достаточно большом п , приращение счетчика J от ехра (к) до ехра (K +1) принимает порядка C × ехра (к)/k итерации (для постоянных C & approx; (1 − exp (− 1))/5, если я не ошибаюсь).Позволить ч = CEIL (журнал (п)), приращение счетчика от 1 до п таким образом, занимает не более

        T = C × (ехр (час)/ч + ехр (ч − 1)/(ч − 1) + exp (h − 2)/(h − 2) + & hellip; + exp (1)/1)

итераций. Для больших п (и, таким образом ч), ведущий ехр (ч)/ч термин должен доминировать над остальными, таким образом, что Т ≤ С × ехр (ч)/ч для некоторой константы C , и, следовательно, цикл должен выполняться в O (ехр (ч)/ч) = O (n/log n) время.

Тем не менее, я признаю, что это всего лишь эскиз доказательства, и в моем аргументе могут быть пробелы или ошибки. В частности, я фактически не определил верхнюю границу константы (?) C . (С = С × ч бы, очевидно, удовлетворяют неравенству, но лишь получением O (п) верхняя граница выполнения; С = С/(1 − exp (− 1)) дал бы желаемую оценку, но, очевидно, слишком мал.) Таким образом, я не могу полностью исключить возможность того, что фактическая временная сложность может быть (очень немного) выше.