當涉及兩個遞歸調用時計算複雜度

Question

如何計算多個遞歸調用時的複雜度？

如在這個問題。

F(n) 
{ 
    if (n is 1) 
    return; 
    F(n/2) //Call 1 
    F(n/3) //Call 2 
    F(n/6) //Call 3 
} 

Answer 1

你只需要解方程，

T(n)=T(n/2)+T(n/3)+T(n/6)+O(1)

現在，作爲T（N/2）> T（N/3），我們可以改爲解決

T(n)=3T(n/2)+O(1)

使用master's theorem，T（N）= O（N ^（日誌（基數爲2）3））= O（N^1.58）

請注意，可能有更好的解決方案，但因爲這是大O符號，所以這也是有效的

Answer 2

有趣的問題。

我相信我可以證明，這個功能的複雜度爲O（N ^ç）的任何C> 1.

召回大O符號的定義。如果存在常數k和n'，使得對於所有n> n'使得g（n）爲k * f（n），我們說函數g（n）是O（f（n））。 （通俗地說，G（N）由f（n）的用於充分大的n爲上界，忽略常數因子。）

選擇任一C> 1，並觀察，對於足夠大的N，

1>（ 1/2）^ç +（1/3）^ç +（1/6）^ç + 1/n的^ç

這是很容易看到，因爲1/2 1/3 + + 1/6 = 1和（1/2）^c < 1/2等，因爲c> 1。並且當n足夠大時，1/n ^c是任意小的。

乘以通過用n ^Ç，以獲得，對於足夠大的n：

Ñ^Ç>（N/2）^Ç +（N/3）^Ç +（N/6）^ç + 1

因此，如果F（M）的運行時間由米^ç上界爲M = N/2，M = N/3，和M = N/6，那麼F（n）的運行時間以上限爲n ^c。結果歸納如下。因此，雖然我錯誤地認爲這個函數是O（n），但是它是任意接近的......在任何正數值epsilon的意義上，不管它有多小，函數都是O（n ^{1 + epsilon}）。

...

一般來說，對於這種類型的問題，我認爲你想猜想解決方案的形式n ^c，然後嘗試在c上放置一個邊界。這主要是主定理本身是如何工作的。