我正在学习大O符号的运行时间和摊销时间。我理解O（n）线性时间的概念，这意味着输入的大小成比例地影响算法的增长。。。例如，二次时间O（n2）等也是如此。甚至是通过阶乘增长的算法，如置换生成器，其O（n！）次。
例如，以下函数为O（n），因为算法与其输入n成比例增长：
f(int n) {
int i;
for (i = 0; i < n; ++i)
printf("%d", i);
}
类似地，如果存在嵌套循环，时间将为O（n2）。
但O（log n）到底是什么？例如，说一个完整的二叉树的高度是O（log n）是什么意思？
我确实知道（也许不是很详细）对数是什么，从这个意义上说：log10 100=2，但我不知道如何识别具有对数时间的函数。
当前回答
我可以补充一些有趣的东西，很久以前我在科尔曼等的书中读过。现在，想象一个问题，我们必须在问题空间中找到解决方案。这个问题空间应该是有限的。
现在，如果你能证明，在你的算法的每一次迭代中，你都切断了这个空间的一部分，这不小于某个极限，这意味着你的算法在O（logN）时间内运行。
我应该指出，我们这里讨论的是相对分数极限，而不是绝对分数极限。二进制搜索是一个经典的例子。在每一步中，我们都会丢掉1/2的问题空间。但二进制搜索并不是唯一的例子。假设，你以某种方式证明了，在每一步中，你至少丢掉了1/128的问题空间。这意味着，您的程序仍然以O（logN）时间运行，尽管比二进制搜索慢得多。这是分析递归算法的一个很好的提示。通常可以证明，在每一步递归都不会使用几个变量，这会导致问题空间中某些分数的截断。
其他回答
对数运行时间（O（log n））本质上意味着运行时间与输入大小的对数成比例增长-例如，如果10个项目最多需要一定的时间x，100个项目最多花费2倍，10000个项目最多耗费4倍，那么它看起来像是O（log n）时间复杂性。
你可以通过说时间与N中的位数成正比来直观地想到O（log N）。
如果一个操作对输入的每个数字或位执行恒定的时间工作，则整个操作所花费的时间将与输入中的数字或位的数量成比例，而不是与输入的大小成比例；因此是O（log N）而不是O（N）。
如果一个操作做出一系列恒定的时间决定，每个决定将要考虑的输入的大小减半（减少3、4、5…的因子），那么整个过程将花费与输入大小N的对数基2（基3、基4、基5…）成比例的时间，而不是O（N）。
等等
这两种情况需要O（log n）时间
case 1: f(int n) {
int i;
for (i = 1; i < n; i=i*2)
printf("%d", i);
}
case 2 : f(int n) {
int i;
for (i = n; i>=1 ; i=i/2)
printf("%d", i);
}
这仅仅意味着该任务所需的时间随着log（n）的增加而增加（例如：n＝10时为2s，n＝100时为4s，…）。请阅读维基百科关于二进制搜索算法和大O符号的文章以了解更多的精度。
O（logn）是衡量任何代码运行时性能的多项式时间复杂度之一。
我希望你已经听说过二进制搜索算法。
假设您必须在大小为N的数组中找到一个元素。
基本上，代码执行如下N不适用于2不适用于4N/8…等
如果你把每一级所做的所有工作相加，你将得到n（1+1/2+1/4….），等于O（logn）
