理解示例 16 从大 O 符号打印 2 的幂 - 破解编码面试

Question

作者是否错过了计算 I/O 调用？

The following function prints the powers of 2 from 1 through n (inclusive). For example, if n is 4, it would print 1,2, and 4. What is its runtime?

int powersOf2(int n) {
  if (n < 1) {
    return 0;
  } else if (n == 1) {
    System.out.println(1);
    return 1; 
  } else {
    int prev = powersOf2(n / 2); 
    int curr =prev * 2; 
    System.out.println(curr); 
    return curr;
  }
}

the runtime is O(log n)

根据示例 12（字符串排列），System.out.println() 调用的参数长度有意义：

Executing line 7 takes O(n) time since each character needs to be printed

从I/O的角度来看，我们需要打印 2 从 0 到 K 的次方，其中 K 是 [log(N)]，即 2^{X[= 要打印的字符数35=] 是 [1 + X/log(10)]，所以要打印的字符总数是 [K + 1 + K*(K+1)/2log(10)]，运行时间是 O(log²N) 但不是 O(log N )}

PS.

示例 15 - 打印 memoized Fibonacci 数似乎有同样的缺点：

void allFib(int n) {
  int[] memo = new int[n + 1]; 
  for (int i = 0; i < n; i++) {
    System.out.println(i + ": " + fib(i, memo));
  }
}

int fib(int n, int[] memo) {
  if (n <= 0) return 0;
  else if (n == 1) return 1;
  else if (memo[n] > 0) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

We're doing a constant amount of work N times, so this is O(n) time.

前N个斐波那契数列~N²打印的字符数量，所以运行时间应该是O(N²).

Answer 1

你是对的。打印出的字符总数为 Θ(log² n)，因此代码完成的工作总量为 Θ(log² n) 而不是 O(log n)，假设我们计算打印每个字符的成本。在进行粗略的大 O 计算时，忽略打印结果的成本是很常见的，尽管在 Theoryland 中你必须考虑这些成本。

话虽这么说，但可以合理地论证任何 int 值在计算机上打印时都会占用固定数量的字符（在 32 位机器上打印 32 位整数需要最多 11 个字符，在 64 位机器上打印一个 64 位整数最多需要 21 个字符，等等）。因此，您可以争辩说，对于任何固定机器，打印任何整数的成本都是 O(1)，即使实际上有一些辅助参数 w 表示机器字的大小，打印 w 位整数的成本是 O( w).

对于学习推理大 O 的介绍性练习，我认为从教学的角度来说，忽略这个细节是好的。但如果我教授更高级的理论课程，我们肯定需要考虑这些成本。

理解示例 16 从大 O 符号打印 2 的幂 - 破解编码面试

Understanding Example 16 printing the powers of 2 from Big O notation - Cracking the Coding Interview

java

big-o