遞迴式中的變數代換（change of variables）

有些遞迴式無法套進分治模子，因為規模以奇怪的方式縮小——比方是開平方根，而不是除以一個常數。訣竅是把變數改名，讓遞迴式變成你已經會解的熟悉形狀，解完再翻譯回去。

以經典的 T(n) = T(sqrt(n)) + 1 為例。除以平方根，跟主定理所預期的任何東西都不一樣。令 m = log n（等價於 n = 2^m）。則 sqrt(n) = n^(1/2) = 2^(m/2)，所以它的對數是 m/2。定義 S(m) = T(2^m) = T(n)。遞迴式就變成 S(m) = S(m/2) + 1——這我們一眼就認得：由主定理（a=1, b=2, f=Theta(1)）得 S(m) = Theta(log m)。現在翻譯回去：T(n) = S(m) = Theta(log m) = Theta(log log n)。一旦我們在指數上運作，開平方根的縮小就變成了普通的對折。

對於帶有 sqrt(n)、n^(1/k) 或其他非線性規模縮減的遞迴式，變數代換是標準的逃生出口——這一招幾乎總是「取對數，把乘法式的縮小變成加法／對折式的縮小」。誠實的告誡：你也必須轉換基底情況（當 n 很小時，m 是多少？），並且應重新檢視「非完全平方數開根號帶來的取整」會不會造成麻煩（對漸進分析通常不會）。它是一種重新表述，不是新定理：所有功夫都在找出正確的代換，好讓某個已知方法能套用。