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

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步（基本情况-恒定时间）

现在我相信这仍然是O（N），但是如果我说阶乘2更像O（N 1）（其中1是基本情况），而不是阶乘1，它正好是O（N）（包括基本情况），我是对的吗？

Answer 1

我认为不，你这样说是不对的。

如果某物是O（N），那么根据定义它是O（N 1）以及O（2n 3）以及O（6N-e）或O（67777N-e^67）。为了方便记法，我们使用了最简单的形式，但是我们必须注意，可以说第一个函数也是O（N 1），同样地，第二个函数也是O（N）`。

我会证明的。如果你花些时间研究大O的定义，那么证明这一点并不难。g（n）=O（f（n）），f（n）=O（k（n））--暗示-

（不相信我？只需谷歌大O表示法的传递属性）。然后很容易看出下面的含义如下所示。

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

所以说一个函数是O（N）或O（n1）之间绝对没有区别。你刚才说了两次同样的话。这是一个等距，一个同余，一个等价。选一个你喜欢的词。它们是同一事物的不同名称。

如果你看Θ函数，你可以把它们想象成一堆充满函数的数学集合，其中该集合中的所有函数都具有相同的增长率。一些常见的集合包括：

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

一个函数将落入一个且恰好是一个Θ集。如果一个函数分为两个集合，那么根据定义，两个集合中的所有函数都可以同时分为两个集合，并且实际上只有一个集合。最后，Θ将所有可能的函数完美分割为可数无限唯一集。

一个函数在big-O集合中意味着它存在于某个θ集合中，其增长率不大于big-O函数。

这就是为什么我会说你错了，或者至少被误导了，说它是“更多的O（N 1）” 实际上只是一种表示“增长率等于或小于线性增长的所有函数集”的方法。也就是说：

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 2

匿名用户

您的伪代码对于其执行的确切细节仍然相当模糊。一个更明确的可能是

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;
}

因此，我们看到计算阶乘1（n）比计算阶乘1（n-1）多需要四个步骤，计算阶乘1（1）需要两个步骤：

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

这大致可以转化为4n个操作，即O（n）。多出一步或少出一步，或任何恒定的步数（即独立于n），都不会改变任何事情。

Answer 3

需要注意的一点是factorial1对于n=0是不正确的，可能会溢出并最终导致典型实现中的堆栈溢出。factorial2对于n=0是正确的。

撇开这一点不谈，你的直觉是正确的factorial1是O（n），而factorial2是O（n 1）。然而，由于n的影响主导于常数因子（1），通常通过称其为O（n）来简化它。维基百科关于大O符号的文章对此进行了描述：

...出现在O（...）中的函数g（x）通常被选择为尽可能简单，省略常数因子和低阶项。

然而，从另一个角度来看，更准确的说法是这些函数在伪多项式时间内执行。这意味着它相对于n的数值是多项式的，但相对于表示n值所需的位数是指数的。有一个很好的先验答案描述了这种区别。

什么是伪多项式时间？它与多项式时间有何不同？