T (время выполнения) против T (рекурсия) - PullRequest
Новая
       12

T (время выполнения) против T (рекурсия)

1 голос
/ 28 февраля 2020

Я не понимаю, в чем разница между (T) от повторения и (T) от времени выполнения. Я взял несколько курсов, которые учат меня рекурсии и линейной рекурсии, например, в этом коде 

factorial (n) {    
if (n = 0) 
    return 1
else
    return n * factorial(n-1)
}

Почему сложность времени равна O (n)?

Я прошел курс о рецидиве, и я Смущаюсь. Я бы проанализировал код следующим образом: 

Tn = 1 , n=0

Tn = n*T(n-1)

, поэтому, если мы расширим рекурсию: 

Tn = (n-1)*(n)*T(n-2)

, рекурсия будет расти n! и рост составляет O(n!), однако анализ отличается, но что я делаю не так?

И затем у меня есть еще один аналогичный вопрос, я взял курс на линейную функцию повторения и в этом курсе я учусь как решить рецидив, например: f(n) = f(n-1) + f(n-2)

Итак, в программе Фибаничи: 

def Fibonacci(n): 
if n<0: 
    print("Incorrect input") 
# First Fibonacci number is 0 
elif n==0: 
    return 0
# Second Fibonacci number is 1 
elif n==1: 
    return 1
else: 
    return Fibonacci(n-1)+Fibonacci(n-2)

Я бы решил линейную рецидив Фибоначчи с такой близкой формой, как эти: 

1/sqr(5)*(1+sqr(5))/2 *((1+sqr(5))/2)**n  -  1/sqr(5)*(1-sqr(5))/2 *((1-sqr(5))/2)**n

Почему бы не порядок роста? O (1 / sqr (5) * (1 + sqr (5)) / 2 * ((1 + sqr (5)) / 2) ** n)

1 Ответ

2 голосов
/ 28 февраля 2020

Существует разница между значением функции и временем для вычисления этого значения.

Когда вы анализируете свою линейную повторяемость, вы утверждаете, что анализ:

Tn = 1, n = 0 Tn = n * T (n-1)

Но вычисление, включенное в вычисление каждого следующего члена, на самом деле составляет всего 1 (одно умножение) с учетом предыдущих значений. Так что должно быть Tn = 1 + T (n-1). Когда вы повторно запустите анализ, линейный результат станет ясен.

Подобное разделение между значением и временем выполнения поможет вам проанализировать ваш второй вопрос.

...