Почему временная сложность цикла Фибоначчи, используемого для цикла, равна O (n ^ 2), а не O (n)? - PullRequest
Новая
       33

Почему временная сложность цикла Фибоначчи, используемого для цикла, равна O (n ^ 2), а не O (n)?

0 голосов
/ 05 июля 2018

Почему сложность времени рассчитывается как O (n ^ 2) вместо O (n) для алгоритма ниже. 

FibList(n)
    array[0-n] Create Array            O(n)
    F[0] <- 0                          O(1)
    F[1] <- 1                          O(1)

    for i from 2 to n                  O(n)
        F[i] <- F[i-1] + F[i-2]        O(n) 

    return F[n]                        O(1)

O (n) + O (1) + O (1) + O (n) O (n) + O (1) = O (n ^ 2)

1 Ответ

0 голосов
/ 05 июля 2018

Если вы предполагаете, что стоимость добавления целого числа с k1 битами к одному с k2 битами пропорциональна макс. (k1, k2) (которая представляет собой так называемую "битовую" модель стоимости, или «логарифмическая» модель затрат), то временная сложность кода, который вы создали, составляет O (n ^ 2).

Это потому, что F (i) (почти) пропорционален phi ^ i, где phi - Золотое сечение. Это означает, что F (i) имеет ~ i бит.

Итак, стоимость: 

for i from 2 to n
    F[i] <- F[i-1] + F[i-2]

пропорционален (1 + 2 + 3 + ... n-1), который равен n (n-1) / 2 и, следовательно, O (n ^ 2).

Если вы предполагаете, что сложение целых чисел произвольного размера равно O (1), то код O (n).

Сведения о моделях стоимости см. В этом разделе википедии https://en.wikipedia.org/wiki/Analysis_of_algorithms#Cost_models, где написано

Здесь нужно быть осторожным; например, некоторые анализы учитывают сложение двух чисел за один шаг. Это предположение не может быть оправдано в определенных контекстах. Например, если числа участвуют в вычисление может быть сколь угодно большим, время, необходимое для одного сложение больше нельзя считать постоянным.

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

...