Решение рекуррентного уравнения без теоремы Мастера

Итак, на предыдущем экзамене меня попросили решить следующее рекуррентное уравнение без использования основной теоремы:

T(n)= 9T(n/3) + n^2

К сожалению, я не мог понять это на экзамене, поэтому я решил его с помощью Теоремы Мастера, чтобы знать ответ (но, конечно, я не получил зачета за вопрос), и теперь я хотел бы знать, как решить ее без магистерской теоремы, так как на выпускном экзамене будут аналогичные вопросы.

Если бы кто-то мог предоставить пошаговое решение (с объяснением), это было бы блестяще, спасибо!


recurrence big-o master-theorem
person busebd12    schedule 20.02.2015    source источник
comment
Я голосую за то, чтобы закрыть этот вопрос как не по теме, потому что он не о программировании.   -  person    schedule 01.05.2018

Ответы (1)


arrow_upward
9
arrow_downward

Хитрость заключается в том, чтобы продолжать расширяться, пока вы не увидите шаблон.

T(n) 
= 9 T(n/3) + n^2 
= 9(9T(n/3^2) + n^2/3^2) + n^2 
= 9^2 T(n/3^2) + 2n^2
= 9^2 (9 T(n/3^3) + n^2/3^4) + 2n^2
= 9^3 T(n/3^3) + 3n^2
= ...
= 9^k T(n/3^k) + kn^2

Это продолжается до тех пор, пока k не станет таким, что 3^k = n.

Предполагая T(1)=1, вы получаете T(n) = n^2 +kn^2 = n^2 + log_3(n) n^2.

Так что это выглядит как T(n) = O(n^2 logn), если только я не ошибся.

person MarkG    schedule 20.02.2015
comment
О, расширение теперь имеет гораздо больше смысла, спасибо! Однако я все еще не понимаю, как можно предположить, что T(1)=1. - person busebd12; 21.02.2015
comment
Это разумное предположение, поскольку в этом случае рассматриваемый алгоритм, скорее всего, будет работать за постоянное время, то есть T (1) = O (1). - person MarkG; 21.02.2015
comment
Ах, да, это кажется разумным. Итак, можете ли вы просто сделать это предположение для большинства рекуррентных соотношений? - person busebd12; 21.02.2015
comment
Если в задаче не указан другой базовый случай, я думаю, что это предположение нормально. - person MarkG; 21.02.2015