Путаница в отношении временной сложности рекурсивных функций - PullRequest
Новая
       15

Путаница в отношении временной сложности рекурсивных функций

0 голосов
/ 13 мая 2019

В основном рекурсивные функции работают так:

T (функция) = T (рекурсивная часть) + T (остальная часть)

правый

Итак, вот в этом коде: 

int foo(int n){
printf("%d",n);
if(n>0){
     foo(n-1);
     foo(n-1);
}
return 0;
}

Для этого рекурсивное уравнение будет иметь вид: T (n) = 2 * T (n-1) + 2 * C или T (n) = 2 * T (n) + C? Я знаю, что это не имеет никакого значения для общей сложности времени, но требует концептуальной ясности, так как рекурсивная функция вызывается два раза и O (1) для постоянной части каждого, так что на каждом уровне никакие постоянные вызовы не удваиваются, поэтому это 2 * с, верно? Теперь при создании дерева рекурсии рекурсивная часть вычисляется как O (2 ^ n), а константа - как O (n ^ 2), так что T (n) = O (2 ^ n) + O (n ^ 2) = O (2 ^ n), верно?

Теперь, скажем, в другой функции: 

int foo(int n){
int temp = n;
while(--temp>=0) printf("%d",n);
if(n>0){
     foo(n-1);
}
return 0;
}

Здесь T (n) = T (n-1) + n

Рекурсивная часть оценивается как O (n), а постоянная часть - как O (n ^ 2), поэтому общая сложность времени равна O (n ^ 2), верно?

Правильно ли мое понимание? Временная сложность рекурсивной функции = общая стоимость рекурсивных вызовов + общая стоимость в постоянных частях

Скажите, 

T(n) = 2*T(n-1) + O(1); n>1
       O(1) & terminate; n = 1

Здесь, если изначально n = 3, то правильно ли сделать вывод, что общая стоимость понесенных рекурсивных вызовов равна 6 * O (1), а в постоянных частях - 7 * O (1)?

Обычно, когда T (n) ломается до T (n / что-то), я могу применить теорему Матера, но в таких задачах, как этот T (n-что-то), это неприменимо, поэтому я рисую дерево рекурсии и складываю их, Есть ли более простой способ решить проблемы такого типа?

...