递归算法中的基本情况和时间复杂度

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），不会改变任何内容。