时间复杂度的对数函数

Question

程序的最坏情况或平均情况如何依赖于对数函数？ log base 是如何发挥作用的？

Answer 1

当您将问题拆分为 k 个部分时，日志因子出现，每个部分的大小为 n/k，然后对其中的一些部分 "recurse"（或模拟递归）。

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

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

上面会打印出n, n/2, n/4, .... , 1——而且还有O(logn)这样的值。
上述程序的复杂度为O(logn)，因为每次打印都需要一定的时间，并且n 的值的数量是O(logn)

如果您正在寻找 "real life" 个示例，在快速排序中（为简单起见，我们假设拆分为恰好两半），您将大小为 n 的数组拆分为两个大小为 n/2，然后对它们进行递归 - 并在每一半上调用算法。

这使得复杂度函数为：

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

来自master theorem，这是在Theta(nlogn)。

类似地，在二分查找中 - 您将问题分成两部分，并且只对其中之一进行递归：

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

Theta(logn)

基数不是大 O 复杂度的一个因素，因为

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

和 log_2(k) 是常数，对于任何常数 k.

Logarithmic function in time complexity