遞歸算法中的基本情況和時間複雜度

Question

我想對O（N）函數做一些說明。我正在使用SICP。

考慮，在僞代碼生成一個遞歸過程書中的階乘函數：

function factorial1(n) { 
    if (n == 1) { 
     return 1; 
    } 
    return n*factorial1(n-1); 
} 

我不知道如何來衡量的步數。也就是說，我不知道如何「一步」的定義，所以我用的語句從書中定義步：

因此，我們可以計算N！通過計算（n-1）！並將 結果乘以n。

我認爲這是他們的意思一步。對於一個具體的例子，如果我們跟蹤（階乘5），

• 階乘（1）= 1 = 1步驟（基礎案例 - 恆定的時間）
• 階乘（2）= 2 *階乘（1）= 2步驟
• 階乘（3）= 3 *階乘（2）= 3步
• 階乘（4）= 4 *階乘（3）= 4步
• 階乘（5）= 5 *階乘（4） = 5步

我認爲這確實是線性的（數字的步驟與n）成正比。

另一方面，這裏是另一個因素，我看到的基本情況略有不同。

function factorial2(n) { 
    if (n == 0) { 
     return 1; 
    } 
    return n*factorial2(n-1); 
} 

這是完全一樣的第一個，除了另一個計算（步驟）加入：

• 階乘（0）= 1 = 1步驟（基礎案例 - 恆定的時間）
• 因子（1）= 1 *階乘（0）= 2個步驟
• ...

現在我相信這仍然是O（N），但我是正確的，如果我說factorial2更像O（n + 1）（其中1是基本情況），而不是恰好爲O（N）的factorial1（包括基本情況）？

Answer 1

有一點要注意的是，factorial1是不正確的n = 0，可能下溢，最終導致典型的實現堆棧溢出。 factorial2對於n = 0正確。

設置一邊，你的表達是正確的。 factorial1是O（n）並且factorial2是O（n + 1）。然而，由於n的影響優於常數因子（+ 1），因此通過將其簡化爲O（n）來簡化它。上Big O Notation維基百科文章描述的：

...的函數g（x）的O（...）中出現的通常被選擇爲儘可能地簡單，省略常數因子和低階項。

從另一個角度來看，更準確的說這些函數在pseudo-polynomial time中執行。這意味着它是關於數值n的多項式，但是相對於表示值n所需的位數是指數的。有一個很好的事先答案，描述了區別。

What is pseudopolynomial time? How does it differ from polynomial time?

Answer 2

我認爲不，你不會是在說正確的。

如果事情是O(N)那麼它在定義O(N+1)以及O(2n+3)以及O(6N + -e)或O(.67777N - e^67)。我們用最簡單的形式進出方便的符號O(N)然而，我們必須認識到，這將是真正的說，第一個功能也O(N+1)並且同樣地，第二是儘可能多O(n) as it was爲O（n + 1）`。

生病證明這一點。如果你花一些時間來定義big-O，那麼證明這一點並不難。 （n）= O（k（n）） - > g（n）= O（k（n））

我？只是谷歌傳遞財產的大O符號）。從上面可以很容易地看出下面的含義。

n = O(n+1), factorial1 = O(n) --implies--> factorial1 = O(n+1) 

因此，說一個函數是O（N）或O（N + 1）是完全沒有區別的。你只是說了兩次同樣的事情。它是一個等距，一致性，等同性。選擇你喜歡的詞。對於同一件事他們是不同的名字。

如果你看一下，你可以把它們想象成一堆的全功能，其中該組中的所有功能，具有相同的增長率數學套Θ功能。一些常見的集：

Θ(1)  # Constant 
Θ(log(n)) # Logarithmic 
Θ(n)  # Linear 
Θ(n^2)  # Qudratic 
Θ(n^3)  # Cubic 
Θ(2^n)  # Exponential (Base 2) 
Θ(n!)  # Factorial 

函數將陷入之一，只有一個Θ集。如果一個函數落入2個集合，那麼通過定義，兩個集合中的所有函數都可以被證明落入兩個集合中，並且您真的只有一個集合。在這一天結束的時候，Θ給了我們一個完美的將所有可能的函數分割成可數無限唯一集合的集合。

的函數在一個大-O組是指它存在於不具有比大-O功能更大的生長速率一些Θ集。

而這就是爲什麼我會說你錯了，或者至少誤導說這是「更O(N+1)」。 O(N)實際上只是一種說明「增長率等於或小於線性增長的所有函數的集合」的方式。所以說：

a function is more O(N+1) and less `O(N)` 

就等於說

a function is more "a member of the set of all functions that have linear 
growth rate or less growth rate" and less "a member of the set of all 
functions that have linear or less growth rate" 

這是非常荒謬的，不正確的事說了。

Answer 3

你的僞代碼仍然是作爲其執行的具體細節很模糊。更明確的一個可能是

function factorial1(n) { 
    r1 = (n == 1);  // one step 
    if r1: { return 1; } // second step ... will stop only if n==1 
    r2 = factorial1(n-1) // third step ... in addition to however much steps 
          //    it takes to compute the factorial1(n-1) 
    r3 = n * r2;   // fourth step 
    return r3; 
} 

因此我們看到計算factorial1(n)需要四個步驟不是計算factorial1(n-1)，並計算factorial1(1)需要兩個步驟：

T(1) = 2 
T(n) = 4 + T(n-1) 

這意味着大約到4N整體運營，其中是 in O（n）。一步多或少，或任何步數不變（即獨立於n），不會改變任何內容。