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

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

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

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

我不知道如何测量步数。也就是我不知道“step”是怎么定义的，所以我用书上的说法来定义一个step:

Thus, we can compute n ! by computing (n-1)! and multiplying the result by 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);
}

这与第一个完全相同，只是添加了另一个计算(步骤):

现在我相信这仍然是 O(N)，但是如果我说 factorial2 更像 O(n+1)(其中 1 是基本情况)而不是 factorial1 恰好是 O(N)，我是否正确(包括基本情况)？

最佳答案

需要注意的一件事是 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 的值所需的位数的指数。有一个很好的先前答案描述了这种区别。

关于algorithm - 递归算法中的基本情况和时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45309982/