Блог

У меня есть функция :

 int ps (int n) 
{ if (n == 1) return 1; 
 else return (Extra(n)   Ps (n/4)   Ps (n/4)); } 
 

Дополнительный(n) — это O(n)

Я попытался найти T(n) этой функции, которая равна T(n)=T(n) 2 T(n/4), и я вычислил сложность, используя главную теорему, это O(n), но я не знаю, как найти ее сложность, используя обратную подстановку

Во-первых, вы ошибаетесь с точки зрения сложности. Вы не упомянули Extra(n) в письменном виде о сложности времени. Так, T(n) = 2 T(n/4) n . Теперь я думаю, что новый термин рекуррентной сложности легко решить путем подстановки:

 T(n) = 2T(n/4)   n = 2 (2 T(n/8)   n/4)   n = 2^2 T(n/8)   n/2   n =
2^2 (2 T(n/16)   n/8)   n/2   n = 2^3 T(n/16)   n/4   n/2   n
 

Теперь, с помощью математической индукции, если мы предположим n = 2^k , что вы можете найти, что:

 T(n) = n   n/2   n/4   n/8   ...   n/2^k = n (1   1/2   1/4   ...   1/2^k) <= 2n
 

Последняя часть приведенного выше анализа исходит из геометрического ряда суммы с коэффициентом 1/2 . Следовательно, T(n) находится в Theta(n) и. O(n)