Время выполнения программы «Разделяй и властвуй» Фибоначчи

Question

count = 0
def fibonacci(n):
    global count
    count = count + 1
    if not isinstance(n, int):
        print ('Invalid Input')
        return None

    if n < 0:
        print ('Invalid Input')
        return None

    if n == 0:
        return 0

    if n == 1:
        return 1

    fib = fibonacci(n-1) + fibonacci(n-2)
    return fib

fibonacci(8)
print(count)

Я пытался выяснить время выполнения этой программы Фибоначчи. Может ли кто-нибудь помочь мне в решении отношения повторения для того же ..

T (n) = T (n-1) + T (n-2) ... Что будет отсчет времени работы отсюда?

Спасибо ...:)

Answer 1

Я предполагаю, что вы имели в виду «Фибоначчи», где вы сказали «факториал».

На каждом уровне у вас есть два звонка на fibonacci(). Это означает, что ваше время будет O (2 ^ n). Вы можете увидеть это, нарисовав дерево рекурсии.

Более подробное и подробное объяснение см. Вычислительная сложность последовательности Фибоначчи .

Answer 2

Время выполнения составляет 2F (n + 1) - 1 вызов, где n - это n-е число Фибоначчи.

Вот быстрое индуктивное доказательство:

В качестве базового случая, если n =0 или n = 1, тогда мы делаем ровно один вызов, и F (1) = F (2) = 1, и мы имеем, что 2F (n + 1) - 1 = 1.

Для индуктивногошаг, если n> 1, то мы делаем столько вызовов, сколько необходимо для оценки функции на n-1 и n-2.Согласно индуктивной гипотезе, для завершения этого процесса требуется 2F (n) - 1 + 2F (n-1) - 1 = 2F (n + 1) - 2 рекурсивных вызова.Однако, поскольку мы считаем текущий вызов функции, мы добавляем к нему один, чтобы получить 2F (n + 1) - 1, как требуется.

Обратите внимание, что 2F (n + 1) - 1 является выражением дляn-е число Леонардо, где

L (0) = L (1) = 1

L (n + 2) = L (n) + L (n + 1) + 1

Который растет при Θ (Φ ⁿ ), как указывает Саид.Однако этот ответ математически точен.

Это более точная среда выполнения, которая вас интересует, поскольку вам нужно учитывать работу, выполняемую в каждом рекурсивном вызове.Если вы отбросите +1 член, вы просто получите серию Фибоначчи!

Answer 3

вы можете видеть wiki , но простое наблюдение Как вы писали:

 T(n) < 2T(n-1) = 2 * 2 T(n-2) =.... = 2^(n-1)T(1) = 2^(n-1). So T(n) is in O(2^n).

на самом деле вы должны решить x^2 = X + 1, так что x будет phi1 = (1+sqrt(5))/2 или phi2 = (1-sqrt(5))/2, поэтомурезультат равен phi1 ^ n + phi2 ^n, но поскольку phi2 меньше 1 для больших n, мы можем сказать, что это T(n)=phi1^n.

Редактировать: * Но вы можете отредактировать свое текущее решение, чтобы принять O(n) время работы (для запуска цикла с первого элемента).

Answer 4

Посмотрите на это особенно time.clock ().Вызовите часы перед вызовом функции и после, вычислите разницу, и вы получите истекшее время.

Кстати: зачем так много кода для Фибоначчи?

def fib (n): return fib (n - 1) + fib (n - 2) if n > 1 else n