我正在学习大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））本质上意味着运行时间与输入大小的对数成比例增长-例如，如果10个项目最多需要一定的时间x，100个项目最多花费2倍，10000个项目最多耗费4倍，那么它看起来像是O（log n）时间复杂性。
其他回答
完整的二进制示例是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）。
等等
O（logn）有点误导，更准确地说，它是O（log2n），即（以2为底的对数）。
平衡二叉树的高度是O（log2n），因为每个节点都有两个（注意log2n中的“两个”）子节点。因此，具有n个节点的树的高度为log2n。
另一个例子是二进制搜索，它的运行时间为O（log2n），因为在每一步中，您都将搜索空间除以2。
我可以举一个for循环的例子，也许一旦掌握了这个概念，在不同的上下文中理解起来会更简单。
这意味着在循环中，步长呈指数增长。例如。
for (i=1; i<=n; i=i*2) {;}
该程序的O表示法的复杂性为O（log（n））。让我们尝试手动循环（n介于512和1023之间（不包括1024）：
step: 1 2 3 4 5 6 7 8 9 10
i: 1 2 4 8 16 32 64 128 256 512
尽管n介于512和1023之间，但只进行了10次迭代。这是因为循环中的步骤呈指数增长，因此只需要10次迭代就可以到达终点。
x的对数（到a的底）是a^x的反函数。这就像说对数是指数的倒数。
现在试着这样看，如果指数增长非常快，那么对数增长（相反）非常慢。
O（n）和O（log（n））之间的差异是巨大的，类似于O（n（n）与O（a^n）之间的区别（a是常数）。
O（logN）基本上意味着时间线性上升，而N指数上升。因此，如果计算10个元素需要1秒，则计算100个元素需要2秒，计算1000个元素需要3秒，依此类推。
当我们进行分而治之的算法（如二进制搜索）时，它是O（logn）。另一个例子是快速排序，每次我们将数组分成两部分，每次都需要O（N）时间才能找到一个枢轴元素。因此，N O（log N）
