我正在学习大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（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);
}
其他回答
如果你正在寻找一个基于直觉的答案，我想为你提供两种解释。
想象一下一座很高的山，它的底部也很宽。要到达山顶，有两种方式：一种是一条围绕山顶螺旋延伸的专用通道，另一种是切割出的小露台状雕刻，以提供楼梯。现在，如果第一种方式在线性时间O（n）内到达，则第二种方式是O（logn）。想象一个算法，它接受整数n作为输入，并在时间上与n成比例地完成，那么它是O（n）或θ。
对数运行时间（O（log n））本质上意味着运行时间与输入大小的对数成比例增长-例如，如果10个项目最多需要一定的时间x，100个项目最多花费2倍，10000个项目最多耗费4倍，那么它看起来像是O（log n）时间复杂性。
实际上，如果您有一个n个元素的列表，并从该列表中创建一个二叉树（就像在除法和征服算法中一样），您将一直除以2，直到达到大小为1的列表（树叶）。
在第一步，你除以2。然后，您有2个列表（2^1），将每个列表除以2，因此您有4个列表（2*2），然后再进行一次除法，您有8个列表（3^3），依此类推，直到列表大小为1
这给出了一个等式：
n/（2^步）=1<=>n=2^步<=>lg（n）=步
（取每边的lg，lg为对数基数2）
这仅仅意味着该任务所需的时间随着log（n）的增加而增加（例如：n＝10时为2s，n＝100时为4s，…）。请阅读维基百科关于二进制搜索算法和大O符号的文章以了解更多的精度。
大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.
