算法：從CLRS復發關係

Question

我最近試圖解決CLRS的一些復發關係，我注意到一個奇怪的細微差別，同時解決這些方程。我不知道你們中有沒有人注意到這個問題，或者理論上的冠軍可以讓我們更多地瞭解這一點。 （我也有CS學位，但不是理論上的！）。而求解所述主定理復發：

T（N）= A T（N/B）+ F（N）

我注意到，推理是這樣的：

ⅰ）展開一元遞歸樹，我們得到一個^{日誌 _bň}葉節點，其中每個節點所做的工作是Θ（1），得到Θ（N ^{日誌 _b一個}）的所有葉子節點

ii ）對於所有非葉節點，g（n）=Σa ^j f（b/n ^j）其中j總計從0到floor（log _b n-1），其中樹的高度是登錄 _bň

III）現在採取信仰的飛躍：提出索賠，使得f（n）被真正被O包圍（N ^{日誌 _b一個} - ＆小量;對於一些與小量）; > 0

iv）現在根據f（n）求解g（n），並根據g（n）求解T（n）。正如在步驟i中提到的，T（n）實際上是Θ（n ^{log _b a}）+ g（n），所以一旦你有一些g（n）與另一個項結合T（n ）

我用這種方法遇到的麻煩是，這裏的推理是這樣的：看，如果我們假設右邊是X，那麼我們把它插入等式來解決左邊。這不是有點奇怪嗎？是不是這樣的：

考慮：X = 8X - 16

所以讓我們假設X = 4和它放入RHS並求解X，冷靜，看，我們得到了4！ 這絕對是有趣的，但你真的解決了這個問題 - 你爲什麼不猜測X是一個無理數，爲什麼不是一個虛數？

此外，我真的很想知道在哪個數學分支中存在這種類型的推理，因爲我懷疑它是來自該領域的CS。任何想法？我知道，在CS中幾乎99％的數學只是「在某些假設條件下的一些更漂亮的論據形式」（因爲CS專業不能解決傳統意義上的方程），但這種方法看起來很獨特。任何想法？

Answer 1

有趣的跳躍信念步驟是數學歸納的捷徑。基本上，它是這樣的：

• 檢查假設對於某些基本情況（例如，只有一個非葉節點）是否爲真。
• 鑑於n th非基本情況屬實，請確保對非基本情況爲n+1。

通常你可以通過假設你想要證明的是真實的，插入它並顯示它的工作原理來做到這一點。在這個特定的例子中，這是否是這種情況，我不太清楚。

解決這類問題經常會有一些靈感，因爲你必須挑選正確的表單來重現，以便讓歸納步驟起作用，但它通常不會挑選出來的東西空氣;在這種情況下，它是通過仔細檢查葉節點和其他節點之間的關係而產生的非常濃密的空氣中挑選出的東西。