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

Question

我希望您能对O(N)函数进行解释。我正在使用SICP。

考虑书中生成递归过程的阶乘函数的伪代码：

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

我不知道如何测量步骤的数量。也就是说，我不知道“步骤”的定义，所以我使用了书中的语句来定义步骤:

因此，我们可以通过计算(n-1)!并将结果乘以n来计算n!。

我认为这就是他们所说的一步。举个具体的例子，如果我们跟踪(factorial 5)，

- factorial(1) = 1 = 1步(基本情况 - 恒定时间) - factorial(2) = 2*factorial(1) = 2步 - factorial(3) = 3*factorial(2) = 3步 - factorial(4) = 4*factorial(3) = 4步 - factorial(5) = 5*factorial(4) = 5步

我认为这确实是线性的(步骤数与n成比例)。

另一方面，这里是另一个阶乘函数，我一直在看到它，它有稍微不同的基本情况。

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

这段与第一个例子完全相同，只是添加了另一个计算步骤：

• factorial(0) = 1 = 1 步（基本情况 - 常数时间）
• factorial(1) = 1*factorial(0) = 2 步
• ...

现在我认为这仍然是O(N)，但如果我说factorial2更像O(n+1)（其中1是基本情况），而不是factorial1，因为它正好是O(N)（包括基本情况），我的说法是否正确？

- lightning_missile

---

大O符号只关心最高次项。O(n+1)不存在，它是O(n)。 - Eric

@Eric O(N+1)是存在的。是的，O(n+1)与O(n)等价，但在大O符号的定义中，并没有规定O(n+1)比O(n)任何少有效。O(n)显然只是因为方便而更常用了。你所说的有些类似于说2/4不存在，因为它实际上是1/2。 - gbtimmon

Answer 1

您的伪代码仍然对其执行的确切细节非常模糊。更明确的伪代码可能是：

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个操作，总体上是O(n)。再多或再少一步，或者任何常数步骤（即与n无关）都不会改变任何东西。

- Will Ness

---

啊，你说得对。在计算步骤数时，我想你没有计算函数调用、if语句和return语句吧？为什么呢？ - lightning_missile

对于 r2 = factorial1(n-1)，我计算：无论函数调用需要多少步骤，加上赋值。您关于计算函数调用本身的观点是正确的：它增加了1步操作，该常数是与 n 无关的。因此，总步骤可能为 8n - 但仍属于O(n)。 - Will Ness

另一方面，这真的取决于具体的实现方式。例如，在汇编语言中，r1 = (n==1) 可能只需要一条指令。如果要将其视为两个步骤，我们会将 ==1 的测试作为第一步，r1 = 的赋值作为第二步；但在汇编语言中，它们可能都是同一条指令的一部分，因为任何指令都需要将其结果放在某个地方。但正如你提到的，这种不确定性只会为每个 n 添加一个恒定数量的步骤，所以对于渐近分析来说并不重要。 - Will Ness

Answer 2

需要翻译的内容如下：

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

抛开这个问题，你的直觉是正确的。factorial1是O(n)，而factorial2是O(n + 1)。然而，由于n的影响超过常数因子（+ 1），通常将其简化为O(n)。维基百科上关于大O符号的文章描述了这一点：

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

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

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

- Chris Nauroth

Answer 3

我认为你说的不正确。

如果某个东西是O(N)，那么它也可以定义为O(N+1)、O(2n+3)、O(6N + -e)或O(.67777N - e^67)。我们为了方便记号而使用最简单的形式O(N)，但我们必须意识到，第一个函数也可以称为O(N+1)，同样地，第二个函数也可以称为O(n)或O(n+1)。

我会证明这一点。如果你花一些时间研究大O的定义，就不难证明g(n)=O(f(n))，f(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

一个函数会属于一个而且只有一个Θ集合。如果一个函数属于两个及以上的集合，那么按照定义，所有在这些集合中的函数都可以被证明同时存在于它们所属的所有集合中，实际上只有一个集合。最终，Θ将所有可能的函数完美地分成了可数无限个唯一的集合。

一个函数属于大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"

这相当荒谬，不是正确的说法。

- gbtimmon

---

Big-O是一个上界，因此f(n)=n属于O(n)，O(n*n)，O(n!)等。与big-Θ进行比较和对比。 - rici

好的发现！计数器捕捉到了，没有大Θ，只有小写希腊字母theta... [O,o,Θ,Ω,ω] :)。我会立即更新措辞以使其正确。 - gbtimmon

不，没有小的θ，只有大的Θ。 :) - rici

那是一个不必要的混淆表述方式。但从技术上讲是正确的，所以你有这个优势。 - gbtimmon

此外，n log(n) 被称为“线性对数”。 - Will Ness