我正在学习大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（ln n），因为搜索结果如下：
1 2 3 4 5 6 7 8 9 10 11 12
搜索4个会产生3次命中：6次，3次，然后4次。而log2 12=3，这是一个很好的近似值，以多少命中需要。
其他回答
首先，我建议您阅读以下书籍：；
算法（第4版）
下面是一些函数及其预期的复杂性。数字表示语句执行频率。
以下Big-O复杂性图表也取自bigocheatsheet
最后，非常简单的展示展示了它是如何计算的；
剖析程序的语句执行频率。
分析程序的运行时间（示例）。
简单地说：在算法的每一步，你都可以将工作减半。（渐近等价于第三、第四、…）
分而治之范式中的算法具有复杂性O（logn）。这里有一个例子，计算你自己的幂函数，
int power(int x, unsigned int y)
{
int temp;
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temp*temp;
else
return x*temp*temp;
}
从…起http://www.geeksforgeeks.org/write-a-c-program-to-calculate-powxn/
O（logN）基本上意味着时间线性上升，而N指数上升。因此，如果计算10个元素需要1秒，则计算100个元素需要2秒，计算1000个元素需要3秒，依此类推。
当我们进行分而治之的算法（如二进制搜索）时，它是O（logn）。另一个例子是快速排序，每次我们将数组分成两部分，每次都需要O（N）时间才能找到一个枢轴元素。因此，N O（log N）
我想补充一点，树的高度是从根到叶的最长路径的长度，节点的高度是该节点到叶的最大路径的长度。路径表示在两个节点之间遍历树时遇到的节点数。为了实现O（logn）时间复杂度，树应该是平衡的，这意味着任何节点的子节点之间的高度差应该小于或等于1。因此，树并不总是保证时间复杂度O（log n），除非它们是平衡的。实际上，在某些情况下，在最坏情况下，树中搜索的时间复杂度可能为O（n）。
你可以看看平衡树，比如AVL树。这项工作是在插入数据时平衡树，以便在树中搜索时保持（logn）的时间复杂度。
