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

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

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

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

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



我认为这就是他们所说的一步。对于一个具体的例子，如果我们追踪(阶乘 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);
}

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

阶乘 (0) = 1 = 1 步(基本情况 - 恒定时间)

factorial(1) = 1*factorial(0) = 2 步

...

现在我相信这仍然是 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 的维基百科文章描述了这一点:



不过，从另一个角度来看，更准确地说这些函数是在 pseudo-polynomial time 中执行的。这意味着它对于 n 的数值是多项式的，但对于表示 n 的值所需的位数是指数的。有一个很好的先前答案描述了这种区别。

What is pseudopolynomial time? How does it differ from polynomial time?

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