Объяснение временной сложности Fib (n)

Question

Я очень хорошо знаю, что рекурсивный Fib (n) имеет временную сложность O (2 ^ n). Я также могу прийти к этому результату, решив следующее

T(n) = T(n-1)+T(n-2).

Но когда я беру пример, я застреваю. Например: n = 4 a cc для рекурсивного решения

T(1) = u #some constant 
and, T(2) = u #some constant
Now, T(4) = T(3)+T(2)
          = T(2)+T(1)+u
          = u+u+u 
          = 3u

Я ожидал, что результат будет 16u.

Answer 1

Обозначение Big-O связано с асимптотической сложностью c, поэтому нас интересует, как сложность растет для больших чисел.

На самом деле Big-O относится к верхнему пределу роста функция. Формально O(g) - это набор функций, которые растут не быстрее, чем k*g.

Позвольте мне привести несколько примеров функций, которые находятся в O(2^n):

• 2 ^ n
• 2 ^ n - 1000000000000n
• 2 ^ n - 100
• 2 ^ n + 1,5 ^ n + n ^ 100

Тот факт, что T(n) in O(2^n) не означает, что количество операций будет точно 2^n.

Это означает лишь то, что предел супремума последовательности |T(n)/(2^n)| равен * 1025. * конечно.