重命名變量來解決遞歸方法

Question

我知道重命名一個正在改變的復發一個你以前見過的變量的想法。

我用幻燈片，直到4號線OK ..他們改名爲T（2 ^米），S（M）>>這意味着他們取得2^M =

所以S（M）應： S（M）= 2T（平方公尺（0.5））+ M

也英里覺得我們不應該離開米，因爲它是，因爲它在這裏的意思是2^M，但他們在現實不是

任何人都可以向我解釋這個嗎？

而且我該如何知道我應該使用哪些變量來讓我更容易？在那裏你權利要求你說

Answer 1

一切都正確達點，由於S（M）= T（2^米），則m = 2^米。定義S（m）= T（2 ^m）的步驟類似於根據舊函數f定義一些新函數g。例如，如果你定義了一個新函數g（x）= 2f（5x），那麼你並不是說x = 5x。你只是定義一個以f來評估的新函數。

讓我們看看這裏發生了什麼。我們已經定義了S（m）= T（2 ^m）。這意味着，

S（M）= T（2^米）

= 2T（√（2^米））+ LG（2^米）

我們可以做一些代數簡化地看到，

S（M）= 2T（2 ^{米/ 2}）+米

而且，使用t和s之間的連接，我們看到，

S（M）= 2 S（M/2）+ M

請注意，我們最終以復發S（m）= 2S（m/2）+ m而不是用原始復發中的S代替S，而是通過進行代數替換和簡化。

一旦我們在這裏，我們可以使用主定理解決S（M）和獲取S（M）= O（M登入），所以

T（N）= S （lg n）= O（lg n lg lg n）。

至於你如何首先想到這個 - 只需要練習。關鍵的見解是，要使用主定理，您需要每次都將問題的大小縮小一個常數因子，因此您需要找到一個將平方根轉換爲常數的轉換。平方根是一種指數運算，對數是專門設計用來將冪運算轉換爲乘法和除法運算的，因此嘗試使用對數或指數替換是合理的。現在你知道這個技巧了，我懷疑你會在更多的地方看到它。

Answer 2

你可以，作爲替代方案，也只是數（N）除以第一個方程得到

T(n)/log(n)=T(sqrt(n))/log(sqrt(n)) + 1 

，然後只用

S(n) = T(n)/log(n) with S(n) = S(sqrt(n)) + 1 

或以不同的方式

S(k) = T(n^(2^(-k)))/log(n^(2^(-k))) 

然後

S(k+1)=S(k)+1 

又是一個衆所周知的遞歸方程。