У меня есть вопрос.
В моей книге они повторяются:
T(n) = 3*T(floor(n/4))+theta(n^2)
Они пытаются угадать, что T (n) = O (n ^ 2), и затем используют метод подстановки, чтобы проверить предположение. Но они не показывают базовый случай? Разве это не нужно?
Я думаю, может быть, это потому, что они не знают, что происходит с T (n), когда n = 1. ??
В моей книге они также встречаются T(n)=2*T(floor(n/2))+n and T(1)=1
Затем они догадываются, что T(n)=O(n lg n)
И они используют метод подстановки, чтобы проверить это.
Они предполагают, что T(n)=O(n lg n) for all positive m<n
T(n) <= 2(c*floor(n/2)*lg(floor(n/2))+n
<= c*n*lg(n/2)+n
= c*n*lg(n)-c*n*lg(2)+n
= c*n*lg(n)-c*n+n
<= c*n*lg(n)-c*n+n
Where c>=1
Ok. Затем они говорят: «Математическая индукция требует, чтобы мы показали, что наше решение верно для граничных условий»
T(1)<=c*1*lg(1)=0
что не соответствует T(1)=1
, но затем они используют асимптотические обозначения, требующие от них только доказать T(n)<= c*n*lg(n) for n>=n0, где они выбирают n0
Затем они заменяют T (1) на T (2) = 4 и T (3) = 5 в качестве базовых случаев в индуктивном доказательстве, позволяя n0 = 2
И мой вопрос:
Почему я должен заменить базовый вариант T (1) на T (2) И T (3)? Почему бы просто не заменить его на T (2) = 4
Я могу вывести T (2) = 4 из повторения и затем сказать
T(2)<= c*2*lg(2) = c*2
Where c>=1 and I choose c>=2
Почему я должен учитывать T (3)?