Анализ сложности кода (Фибоначчи серии)

Question

Это итеративный вариант расчета ряда Фибоначчи в Python:

def fib_iterative(n): 
    if n == 0: 
     return [] 
    if n == 1: 
     return [1] 
    if n == 2: 
     return [1,1] 
    fib_list = [1,1] 
    for i in range(0,n): 
     fib_list.append(fib_list[i]+fib_list[i+1]) 
    return fib_list 

Это рекурсивная версия:

def fib_recursive(n): 
    if n == 1: 
     return 1 
    elif n == 2: 
     return 1 
    else: 
     return fib_recursive(n-1) + fib_recursive(n-2) 

def fib_numbers_in_list(n): 
    fibn = [] 
    for x in range(1,n+1): 
     fibn.append(fib_recursive(x)) 
    return fibn 

Что такое Big-О каждый?

Звонки - это fib_numbers_in_list (n) и fib_iterative (n), чтобы возвращать первые n чисел Фибоначчи в списке.

Есть ли способ, которым мы можем найти алгоритм O (log n) для создания n чисел Фибоначчи?

Answer 1

Вы можете посмотреть на большой нотации O для различных операций питона здесь, чтобы оценить временную сложность: TimeComplexity

И вот пример:

example

Answer 2

def fib_iterative(n): 
    if n == 0: 
     return [] 
    if n == 1: 
     return [1] 
    if n == 2: 
     return [1,1] 
    fib_list = [1,1] 
    for i in range(0,n): 
     fib_list.append(fib_list[i]+fib_list[i+1]) 
    return fib_list 

Эта функция имеет один для цикла, который повторяет n раз. Это делает функцию O(n) временной сложностью.

def fib_recursive(n): 
    if n == 1: 
     return 1 
    elif n == 2: 
     return 1 
    else: 
     return fib(n-1) + fib(n-2) 

def fib_numbers_in_list(n): 
    fibn = [] 
    for x in range(1,n+1): 
     fibn.append(fib_recursive(x)) 
    return fibn 

Я думаю, что есть ошибка вызова fib(n-1) + fib(n-2) в коде. Я предполагаю, что это должно быть fib_recursive(n-1) + fib_recursive(n-1).

Предположим, что fib_recursive(n) имеет f(n) расчетов. Простым уравнением для оценки было бы f(n) = f(n-1) + f(n-2). И граничные условия будут f(2) = 1, f(1) = 1. Это хорошо знакомо с вами? Сложность времени для рекурсивного кода в конечном итоге будет такой же, как и число фибоначчи ввода n.

Как вы уже знаете, n-е число Фибоначчи пропорционально (2.736) ** n. Это усложняет временную сложность рекурсивной функции до O(2.736 ** n). (Если вы хотите получить дополнительную информацию об этом, посетите http://mathworld.wolfram.com/FibonacciNumber.html)

Ну, мы еще не закончили. Мы должны умножить его на n, так как вы хотите знать все числа Фибоначчи от 1 до n. Поэтому щедрый расчет сделает ответ O(n * 2.736 ** n)