algorithm - 如何知道大 O 何时是对数？

Question

我的问题来自“Big O 的简单英语解释”一文。我不知道对数复杂度的确切含义。我知道我可以在时间和操作次数之间进行回归并计算 X 平方值，从而确定复杂度。但是，我想知道一种在纸上快速确定它的方法。

你如何确定对数复杂度？有一些好的基准吗？

Answer 1

不严谨，但如果你有一个算法，基本上将每次迭代需要完成的工作分成一半，那么你就有对数复杂度。经典的例子是二分查找。

Answer 2

不确定这是否是您的意思，但是...当您使用像平衡二叉树这样的分散数据结构时，通常会出现对数复杂性，其中包含根节点的 1 个节点、2 个子节点、4 个孙子节点、8 个曾孙等。基本上在每个级别上，节点的数量都会乘以某个因子（2），但迭代中仍然只涉及其中一个。或者作为另一个例子，一个循环，其中索引在每一步都加倍：

for (int i = 1; i < N; i *= 2) { ... }

类似的事情是对数复杂度的特征。

Answer 3

主定理通常有效。

Answer 4

这是另一种说法。

假设您的算法在问题大小的位数上是线性的。所以，也许你有一个新的算法来分解一个大数，你可以证明它在位数上是线性的。因此，使用您的算法计算 20 位数字所需的时间是 10 位数字的两倍。这将具有日志复杂性。（这对发明者来说是值得的。）

二分法具有相同的行为。将区间长度缩短 1024 = 2^10 大约需要 10 个二等分步骤，但只需 20 步即可将区间长度缩短 2^20 倍。

日志复杂性并不总是意味着算法在所有问题上都很快。O(log(n)) 前面的线性因子可能很大。所以你的算法在小问题上可能很糟糕，直到问题规模明显大到其他算法以指数（或多项式）死亡时才会变得有用。

Answer 5

如果您只是想了解对数 Big Oh，请留意在每个重复步骤中您的数据何时减半。

这是因为如果您正在处理的数据是前一步的 1/2 大，则它是一个无限系列。