recursion - Big-O 表示法运行时 : Cracking the Coding Interview example

Question

我主要是想确认一下我的理解。以下是《破解编码面试》中的大 O 表示法问题。答案是运行时间是“O(b) 或 O(n)。递归代码迭代 b 调用，因为它在每个级别都减一。”

所以我知道函数的 power(a, b-1) 部分等于 O(b) 或 O(n)。 那么“a * power(a, b-1)”行中的第一个“a”会是常数吗？

我知道当我们有像 O(constant * b) 这样的大 O 时，我们必须删除常量，它就变成了 O(b)。

int power(int a, int b){ 
    if(b < 0)
       return 0; //error
    else if(b == 0)
       return 1; 
    else
       return a * power(a, b-1)
 }

Answer 1

您的power函数只是计算某个输入整数a的b次方的幂。它只需将 a 乘以自身 b 次，然后返回该值即可实现此目的。函数调用次数实际上与a 的值无关，而仅与b 的值有关。因此，该函数的行为类似于 O(b)。我们还可以将 b 重命名为 n 并将其称为 O(n)，这可能是您更有可能看到的。