通過歸納驗證重現關係

我一直在接受隨我接受的課程的作業時遇到問題。所討論的分配：通過歸納驗證重現關係

使用感應來證明是當n> = 2爲2的精確的功率，的溶液中的復發：

T(n) = {2 if n = 2, 
     2T(n/2)+n if n =2^k with k > 1 } 
is T(n) = nlog(n)

注：在分配的對數有基2.

這裏的基本情況是顯而易見的，當n = 2時，我們有2 = 2log（2）但是，我被困在這裏的一步，我不知道如何解決這個問題。

來源

2012-02-12 Zilarion

這個問題屬於http://math.stackexchange.com/ – 2012-02-12 11:18:01

總是嘗試接下來的幾個值，如果他們也遵循相同的模式。你知道下一個要考慮的值。然後 - 試着看看這個聲明是否適合它。注：該聲明僅適用於兩項權力。 – 2012-02-12 11:18:12

@亞歷克斯，謝謝我甚至不知道這個網站存在。 – Zilarion 2012-02-12 11:19:55

一步。讓我們假設這個陳述對於所有的m都是2^m，並且讓我們將它表示爲2^{k + 1}。然後，T（2^{k + 1}）= 2T（2^k）+ 2^{k + 1}。通過歸納假設T（2^k）= 2^k * log（2^k），即T（2^k）= k * 2^k（因爲對數在此具有基數2）。因此，T（2^{k + 1}）= 2 * k * 2^k + 2^{k + 1} = 2^{k + 1} *（k + 1），其可以是寫爲2^{k + 1} * log（2^{k + 1}），完成證明。

來源

2012-04-08 09:55:25

通過歸納驗證重現關係

回答

相關問題