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

Question

我想对 O(N) 函数进行一些说明。我正在使用 SICP.

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

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

我不知道如何计算步数。就是不知道"step"是怎么定义的，所以我用书上的说法定义了一个步骤：

Thus, we can compute n ! by computing (n-1)! and multiplying the result by n.

我以为这就是他们所说的一步的意思。举个具体的例子，如果我们追踪 (factorial 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 是基本情况）而不是 factorial1 正好是 O( N)（包括基本情况）？

Answer 1

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

是正确的

撇开这个不谈，你的直觉是正确的。 factorial1 是 O(n)，factorial2 是 O(n + 1)。但是，由于 n 的影响优于常数因子（+ 1），因此通常将其简化为 O(n)。 Big O Notation 上的维基百科文章描述了这一点：

...the function g(x) appearing within the O(...) is typically chosen to be as simple as possible, omitting constant factors and lower order terms.

不过从另一个角度来说，更准确的说法是这些函数在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)`。

我会证明的。如果您花一些时间了解大 O 的定义，那么证明这一点并不难。 g(n)=O(f(n)), f(n) = O(k(n)) --implies-> g(n) = O(k(n))

（不相信我？只是大 O 表示法的 google 传递属性）。然后很容易看出下面的含义是从上面得出的。

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 个集合，那么根据定义，两个集合中的所有函数都可以被证明属于两个集合，而你实际上只有一个集合。在一天结束时，Θ 给了我们一个完美的分割，将所有可能的功能分成可数无限的独特集合。

一个函数在big-O集中意味着它存在于某个增长速度不大于big-O函数的Θ集中。

这就是为什么我会说你错了，或者至少是被误导了 "more O(N+1)"。 O(N) 实际上只是一种标记 [=49=] 的方式。所以说：

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），不要改变任何东西。

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

base case and time complexity in recursive algorithms

algorithm

recursion

performance

big-o

sicp