我正在学习大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。因此，树并不总是保证时间复杂度O（log n），除非它们是平衡的。实际上，在某些情况下，在最坏情况下，树中搜索的时间复杂度可能为O（n）。
你可以看看平衡树，比如AVL树。这项工作是在插入数据时平衡树，以便在树中搜索时保持（logn）的时间复杂度。
其他回答
这仅仅意味着该任务所需的时间随着log（n）的增加而增加（例如：n＝10时为2s，n＝100时为4s，…）。请阅读维基百科关于二进制搜索算法和大O符号的文章以了解更多的精度。
如果您有一个函数需要：
1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2^n elements.
然后需要log2（n）时间。广义地说，大O符号意味着关系只需要对大n成立，常数因子和小项可以忽略。
这个问题已经有了很多好的答案，但我相信我们真的错过了一个重要的答案，那就是图解的答案。
说一个完整的二叉树的高度是O（logn）是什么意思？
下图描述了一个二叉树。请注意，与上面的级别相比，每个级别包含的节点数量是两倍（因此是二进制的）：
二进制搜索是一个复杂度为O（logn）的示例。假设图1中树底部的节点表示某个排序集合中的项目。二进制搜索是一种分而治之的算法，图中显示了我们需要（最多）4次比较才能找到我们在这个16项数据集中搜索的记录。
假设我们有一个包含32个元素的数据集。继续上面的图，发现我们现在需要5次比较才能找到我们正在搜索的内容，因为当我们乘以数据量时，树只增长了一层。结果，该算法的复杂性可以用对数级数来描述。
在一张普通纸上绘制对数（n）将生成曲线图，其中曲线的上升速度随着n的增加而减慢：
大O符号仅供参考。这可能会有所帮助！
大O----------------排序---------------复杂性
O(log N) -Binary search - logarithmic
O(N) -Simple search - Linear
O(N*log N) -Quicksort - loglinear
O(2^N) -recursive - Exponential
O(N2) -Selection sort - directly proportional to the square of the input size.
O（logn）是衡量任何代码运行时性能的多项式时间复杂度之一。
我希望你已经听说过二进制搜索算法。
假设您必须在大小为N的数组中找到一个元素。
基本上，代码执行如下N不适用于2不适用于4N/8…等
如果你把每一级所做的所有工作相加，你将得到n（1+1/2+1/4….），等于O（logn）
