Сложность формула этого алгоритма

Question

Итак, у меня есть этот алгоритм (золотое сечение):

public static float golden(int n){ 

float res; 

if(n == 0){ 
    res = 1; 
} else { 
    res = (float) (1.0 + (1.0/golden(n-1))); 
} 
return res; 

} 

Я полагаю, что Т (п) формула Т (п-1). Таким образом, я могу получить сложность следуя этой формуле ...

Т (п) = аТ (п - Ь) + с^нп (п)

... и это одна:

Но, что такое p (n) и c?

Я надеюсь, что кто-то может мне помочь.

Заранее благодарен!

Answer 1

Для каждого п> 0 вызов golden(n) результатов в постоянном количестве арифметических операций и один рекурсивного вызова, поэтому вы можете написать повторения для функции временной сложности Т (п), как

Т (п) = Т (п-1) + к, п> 0

где к это число операций в каждом вызове. Это отношение повторения для последовательного поиска.

Теперь вы можете применить формулу, которую вы упомянули в вопросе. Напомним, что d в формуле представляет собой степень многочлена p (n). Здесь

а = 1, с = 1, Ь = 1, а р (п) = к,

поэтому d = 0, то теперь, применяя вашу формулу вы получаете а = с^Ь, и, следовательно, применяется второй случай, так что

Т (п) = Тета (п^{d + 1} с^п) = Theta (п).

Это дает окончательный ответ T (n) = Theta (n).