Какова стоимость времени выполнения следующего алгоритма?

Question

for i=2 to n 
    j=3n 
    while j>=1 do 
     j=j/3 

Какова будет временная стоимость данного алгоритма? Не могли бы вы описать пошаговое решение.

Answer 1

Для того, чтобы рассчитать сложность времени, вы обычно перемещаетесь от внутренних петель к внешним контурам.

В настоящее время внутренний один представляет собой цикл while. Она заканчивается, когда j < 1, это имеет место после того, как O (журнал 3n) шаги или O (1 + 3 войти п) или O (журнал п). Обратите внимание, что здесь мы используем n: счетчик контуров i внешнего контура здесь не играет.

наружной петля с другой стороны итеративна O (N-1) раз, или таким образом O (N) раз и каждый раз, когда он делает то же самое количество работы: O (журнал n). Таким образом, общая сумма баллов равна O (n log n).

Вы можете уронить 3 в журнале, так как O (журнал _к п) является O (журнал N) для фиксированного K. Таким образом, более удобная нотация: O (n log n).