Большое время работы этого алгоритма

Question

Мне сложно анализировать временную сложность алгоритмов. Возьмем в качестве примера этот алгоритм, как мне найти время работы в O-записи?

loop(n) 
i = 1 
while i ≤ n 
    j = 1 
    while j ≤ i 
     j = 2 ∗ j 
    i = i + 1 

Answer 1

С вашего поста я понял, что вы знаете о значении нотации O, но имеете некоторые проблемы с его применением. Здесь в этом простом примере достаточно определить, сколько раз (в зависимости от вашего размера ввода) выполняются циклы. Чтобы получить окончательное значение, вы должны объединить его.

Первый шаг: проанализировать время выполнения за цикл. (Без петли или рекурсивные утверждения имеют O (1).)

while(i<=n) 
... 
i=i+1 

выполняется п раз, таким образом, О (п)

Внутренний цикл в то время как (J < = я) J = J * 2

Выполняется i/2 раза, но ограничено n из внешнего контура. Таким образом, это O (n).

Как есть внутренняя петля с использованием O (N) во внешнем контуре нужно умножить asymptitics, то есть п * п => О (п^2)

Answer 2

Когда данный код, как это, он часто помогает работать изнутри. Ваша внутренняя петля приведена здесь:

j = 1 
While j <= i 
    j = 2 * j 

Эта петля работает, повторяя удвоение j до тех пор, пока оно не станет больше i. Количество раз, когда вы можете удвоить 1 до превышения i, составляет Θ (журнал i), поэтому каждый раз, когда выполняется внутренний цикл, выполняется Θ (log i).

Внешний цикл подсчитывает от 1 до п, так что работа является

журнал 1 + 2 + журнал ... + журнал п

= LOG (1 * 2 * .. . * n) (используя свойства логарифмов).

= лог (п!)

= Θ (п § п).

Этот последний шаг следует из Stirling's approximation.

Таким образом, общая сложность времени составляет Θ (n log n).