這是什麼遞歸算法

Question

的大O我們有大小n

是遞歸解決大小爲n的子問題的算法的問題 - 1和解決方案執行 工作的線性量。

我試過使用插件n chug，發現big-O是n，線性的，但是這對我來說似乎不太合適。我還能嘗試什麼？

Answer 1

用於通過你提到的遞歸公式爲：

• T（N）= T（N-1）+ O（n）的

它意味着：

（n-1）+ k（n-2）+ .. + k，這等於k * n *（n + 1）/ 2。

因此，該算法的複雜度爲O（n ）。

Answer 2

在數學堆棧交換的人可能會做得比我更好，但我會給它一個鏡頭。

該算法的描述是不明確的，因此有兩種可能性：

1. 該算法執行的工作對於每個子問題的恆定量。 在這種情況下，該算法實際上將運行在O(n)時間（技術上 2n，但常數因子被忽略）。
2. 該算法爲每個子問題執行線性工作量。 在這種情況下，您正在尋找一個線性循環，每個線程都執行 。 n執行，n每次執行的工作= O(n^2)。 很顯然，每次連續執行都會減少工作量，假設我記得問題模式正確的話，這將在重複關係解決方案中顯示爲 T(n) = (1/2)n^2。