Блог

У меня вопрос.

В моей книге они имеют следующее повторение:

 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
  

ОК. Затем они говорят: «Математическая индукция требует, чтобы мы показали, что наше решение выполняется для граничных условий»

 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)?

Во-первых, как вычислить T (6)? T (6) = 2* T(этаж(6/2)) 6 => T (6) = 2* T (3) 6 = 16.

Во-вторых, они написали, что после n > 3 это становится независимым от T (1) … итак, после 1 и до 4 все должны быть указаны как базовые случаи.

Вот почему у нас есть 2, также введите T (3).

Пожалуйста, прокомментируйте…