大 O 符号运行时：破解编码面试示例

Question

我主要是想确认一下我的理解。以下是 Cracking the Coding Interview 中的大 O 符号问题。答案键说运行时是 "O(b) or O(n). The recursive code iterates through b calls, since it subtracts one at each level."

所以我明白函数的 power(a, b-1) 部分等于 O(b) 或 O(n)。 那么第一个 "a" 是第 "a * power(a, b-1)" 行中的常量吗？

我知道当我们有一个像 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)，这可能是您更可能看到的

Answer 2

我认为最清楚的解释方法是指出 "a" 是一个变量。您没有执行某些计算机指令 "a" 次。

也可以看到"b"也是一个变量。但是在"b"的情况下，它还控制着你的递归函数被调用的次数。所以你确实必须执行一些计算机指令 "b" 次。只要该值不变，多少条指令并不重要。您的程序没有其他变量会影响执行的指令数。

假设您的 n = b，那么您的函数是 O(b) 或 O(n)（因为这是影响程序完成所需时间的输入。）

请记住，这都是关于估计必须执行的指令数。

大 O 符号运行时：破解编码面试示例

Big-O notation runtime: Cracking the Coding Interview example

recursion

runtime

big-o

coding-efficiency