如何知道Big O何时是对数？

Question

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

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

Answer 1

虽然不严谨,但是你有一个算法,它基本上将每次迭代需要完成的工作分成两半,然后你就具有对数的复杂性.典型的例子是二分搜索.

Answer 2

不确定这是不是你的意思,但是......对数复杂性通常出现在你使用扩展数据结构时,比如平衡二叉树,它包含1个根节点,2个孩子,4个孙子,8个基本上在每个级别节点的数量乘以某个因子(2)但仍然只有其中一个参与迭代.或者作为另一个例子,一个循环,其中索引在每一步加倍:

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

这样的事情是对数复杂性的签名.

Answer 3

主定理通常有效.