时间复杂度中的对数函数

Question

程序的最坏情况或平均情况如何与对数函数相关？对数的底数如何发挥作用？

- wahnik

Answer 1

当你将问题分成 k 个部分，每部分的大小为 n/k，然后对其中一些部分进行“递归”（或模拟递归）时，就会出现对数因子。

一个简单的例子是以下循环：

foo(n):
  while n > 0:
     n = n/2
     print n

上面的代码将打印出 n, n/2, n/4, .... , 1 这些值，总共有 O(logn) 个这样的值。
该程序的复杂度为 O(logn)，因为每次打印都需要固定的时间，而沿途要经过的值的数量是 O(logn)。

如果你正在寻找“现实生活”例子，在快速排序中（简单起见，假设将数组精确地分成两半），你将一个大小为 n 的数组分成两个大小为 n/2 的子数组，然后对它们进行递归，并且在每个子数组上调用算法。

这使得复杂度函数为：

T(n) = 2T(n/2) + O(n)

根据主定理，时间复杂度为 Theta(nlogn)。

同样，在二分查找时，将问题分成两部分，仅对其中一个进行递归：

T(n) = T(n/2) + 1

这部分将会在 Theta(logn) 的时间复杂度内完成。

---

在大O复杂度中，底数不是一个因素，因为

log_k(n) = log_2(n)/log_2(k)

并且对于任意常数k，log_2(k)是一个定值。

- amit

---

这个简单的函数示例非常棒。下次有人问我这个问题时，我会用它来引导。我通常使用归并排序作为例子。 - Jim Mischel

“print n” 是 O(1) 还是 O(logn)？ - nymk

@nymk 这将取决于您的假设。通常我们假设处理整数是 O(1)。然而，从理论上讲 - 是的，对于任何大小和无界整数，它将是 O(logN)，因为一个整数 N 需要 O(logN) 位/数字来表示。 - amit

我意识到你示例中的 print n 不是 O(logn)，因为 n 会被反复除以2。 - nymk

对于一般情况，其中打印不是常数，时间复杂度为O((logN)^2)。假设打印的是位（为简单起见），那么每轮你都会移除一个位，这意味着你要打印 log(n) + log(n/2) + log(n/4) + ... + 1 = log(n) + (log(n)-1) + (log(n)-2) + ... + 1 这是等差数列，其和为O(log(n)^2)。 - amit