Я работал над вопросом о домашнем задании, который требует от меня сравнения nlogn и повторения ниже. Как и в том, является ли nlogn нижним, верхним или узким, ограниченным временной сложностью ниже.решение временной сложности рекуррентного отношения?
| 5 n = 1
--| 2T(n/2) + n n > 1
Я думаю, 2Т (п/2) + п уменьшить до NlogN, но я точно не знаю, как решить рекуррентное соотношение ..
Спасибо за вашу помощь.
решить повторения (я надеюсь, что я сделал это право):
2T(n/2) + n
2[2T(n/4) + n/2] + n
2^2*T(n/2^2) + 2n
you find the pattern if you keep on substituting new n
2^k*T(n/(2^k)) + kn
at this point you solve for closed form using the base case then n = 1
so for n/n = 1, we set 2^k = n, so k = logn
sub in k
2^(logn) * T(1) + (logn) * n
note that 2^logn = n with base 2 and T(1) = 5 for the base case
so we obtain 5n + nlogn
5n + nlogn is just O(nlogn)
Поскольку мы имеем и как O (NlogN), она является жесткой границей или большой тета.
В качестве альтернативы вы также можете использовать основную теорему, чтобы легко вычесть сложность. Если вы это узнали.
a = 2
b = 2
c = 1
выше удовлетворяет случай 2, который Θ (NlogN), обратитесь к вики https://en.wikipedia.org/wiki/Master_theorem
Позвольте мне понять, что вы сделали. спасибо – bychit
Краткий ответ. Вы можете (и должны) использовать «Мастер-теорему», чтобы найти O-нотацию для этого повторения.
Мастер-теорема - удобный инструмент для решения проблем, и это должен быть ваш первый вариант, так как вы можете быстро получить результат. Вы можете получить практический с этим exercise
Вы пробовали рекуррентные деревья? – synchronizer
не слишком уверен. В моей книге много доказательств с дискретной математикой – bychit
рекурсивное дерево также должно дать результат. вы можете легко найти результат, так как это популярный и простой приятный повтор –