以下僞代碼的大O複雜度是什麼？

下面的計算複雜度是多少僞代碼？以下僞代碼的大O複雜度是什麼？

integer recursive (integer n) { 
    if (n == 1) 
     return (1); 
    else 
     return (recursive (n-1) + recursive (n-1)); 
}

在現實世界中，調用將得到優化，併產生線性複雜，但與RAM模型上大哦計算，這將是複雜性？ 2^n？

這樣的複雜性似乎是2^n，但可以減少到n。 –

是的，這似乎是'2^n'。 – 2013-11-27 09:36:07

在每次遞歸時，遞歸樹都以2的因子分支。所以在遞歸結束時，你有一個深度爲「n」的完整二叉樹，所以順序是「Θ（2^n）」。 – Shahbaz

該算法目前形式的複雜性確實是O（2 ⁿ），因爲在每個呼叫級別上，呼叫次數都會增加兩次。

第一呼叫（遞歸（N））構成一個呼叫

下一級（遞歸（N-1））構成2個呼叫

在基礎案例（遞歸（1）），它構成2 ^n-1來電。

因此的功能的總呼叫數量是1 + 2 + ... + 2 ^n-1個 = 2 ^Ñ -1

所以複雜度爲O（2 ^Ñ）。

其他景點：

正如你所說，這可以很容易地製成O（n）的（或者是O（log n）的使用快速冪這種特殊情況下）的記憶化，或者動態規劃。

2013-11-27 09:38:56 justhalf

你的複雜性將是 enter image description here

爲什麼會這樣呢？簡單mathematical induction證明：

N = 1：特殊情況下，步數= 1
N = 2，明顯， = 2，所以它的正確
讓它爲N=K，即是正確的對於N=K它將是
假設N=K+1。函數recursive將自動遞歸調用N=K兩次：recursive(K+1) = recursive(K) + recursive(K)，如代碼中所示。那就是：。所以，對於N=K+1我們得到了步驟。

所以我們已經證明了N複雜性將是共用的情況下（從數學歸納法的定義） enter image description here 。

2013-11-27 09:44:27

回答