我正在学习大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，但我不知道如何识别具有对数时间的函数。
当前回答
在信息技术中，它意味着：
f(n)=O(g(n)) If there is suitable constant C and N0 independent on N,
such that
for all N>N0 "C*g(n) > f(n) > 0" is true.
看来这个符号主要是从数学中提取出来的。
本文引用了一句话：D.E.Knuth，《大OMICRON、大OMEGA和大THETA》，1976年：
基于这里讨论的问题，我建议SIGACT以及计算机科学和数学期刊的编辑，采用上面定义的符号，除非有更好的替代方案很快就会发现。
今天是2016年，但我们今天仍然使用它。
在数学分析中，这意味着：
lim (f(n)/g(n))=Constant; where n goes to +infinity
但即使在数学分析中，有时这个符号也用于表示“C*g（n）>f（n）>0”。
我从大学里就知道，这个符号是由德国数学家朗道（1877-1938）创造的
其他回答
O（logn）有点误导，更准确地说，它是O（log2n），即（以2为底的对数）。
平衡二叉树的高度是O（log2n），因为每个节点都有两个（注意log2n中的“两个”）子节点。因此，具有n个节点的树的高度为log2n。
另一个例子是二进制搜索，它的运行时间为O（log2n），因为在每一步中，您都将搜索空间除以2。
完整的二进制示例是O（ln n），因为搜索结果如下：
1 2 3 4 5 6 7 8 9 10 11 12
搜索4个会产生3次命中：6次，3次，然后4次。而log2 12=3，这是一个很好的近似值，以多少命中需要。
你可以通过说时间与N中的位数成正比来直观地想到O（log N）。
如果一个操作对输入的每个数字或位执行恒定的时间工作，则整个操作所花费的时间将与输入中的数字或位的数量成比例，而不是与输入的大小成比例；因此是O（log N）而不是O（N）。
如果一个操作做出一系列恒定的时间决定，每个决定将要考虑的输入的大小减半（减少3、4、5…的因子），那么整个过程将花费与输入大小N的对数基2（基3、基4、基5…）成比例的时间，而不是O（N）。
等等
这仅仅意味着该任务所需的时间随着log（n）的增加而增加（例如：n＝10时为2s，n＝100时为4s，…）。请阅读维基百科关于二进制搜索算法和大O符号的文章以了解更多的精度。
首先，我建议您阅读以下书籍：；
算法（第4版）
下面是一些函数及其预期的复杂性。数字表示语句执行频率。
以下Big-O复杂性图表也取自bigocheatsheet
最后，非常简单的展示展示了它是如何计算的；
剖析程序的语句执行频率。
分析程序的运行时间（示例）。
