我正在学习大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，但我不知道如何识别具有对数时间的函数。
当前回答
下面的解释是使用完全平衡的二叉树来帮助您理解我们如何获得对数时间复杂度。
二叉树是一种情况，其中大小为n的问题被划分为大小为n/2的子问题，直到我们达到大小为1的问题：
这就是你如何得到O（logn），这是在上面的树上需要完成的工作量，以获得解决方案。
具有O（logn）时间复杂度的常见算法是二进制搜索，其递归关系为T（n/2）+O（1），即在树的每个后续级别上，您将问题分成一半，并执行恒定数量的额外工作。
其他回答
如果您有一个函数需要：
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成立，常数因子和小项可以忽略。
如果你在图形计算器或类似的东西上绘制一个对数函数，你会发现它的上升速度非常慢——甚至比线性函数还要慢。
这就是为什么对数时间复杂度算法备受追捧的原因：即使对于真正大的n（例如，假设n＝10^8），它们的性能也超出了可接受的范围。
下面的解释是使用完全平衡的二叉树来帮助您理解我们如何获得对数时间复杂度。
二叉树是一种情况，其中大小为n的问题被划分为大小为n/2的子问题，直到我们达到大小为1的问题：
这就是你如何得到O（logn），这是在上面的树上需要完成的工作量，以获得解决方案。
具有O（logn）时间复杂度的常见算法是二进制搜索，其递归关系为T（n/2）+O（1），即在树的每个后续级别上，您将问题分成一半，并执行恒定数量的额外工作。
这个问题已经有了很多好的答案，但我相信我们真的错过了一个重要的答案，那就是图解的答案。
说一个完整的二叉树的高度是O（logn）是什么意思？
下图描述了一个二叉树。请注意，与上面的级别相比，每个级别包含的节点数量是两倍（因此是二进制的）：
二进制搜索是一个复杂度为O（logn）的示例。假设图1中树底部的节点表示某个排序集合中的项目。二进制搜索是一种分而治之的算法，图中显示了我们需要（最多）4次比较才能找到我们在这个16项数据集中搜索的记录。
假设我们有一个包含32个元素的数据集。继续上面的图，发现我们现在需要5次比较才能找到我们正在搜索的内容，因为当我们乘以数据量时，树只增长了一层。结果，该算法的复杂性可以用对数级数来描述。
在一张普通纸上绘制对数（n）将生成曲线图，其中曲线的上升速度随着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);
}
