我正在学习大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符号仅供参考。这可能会有所帮助！
大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.
其他回答
如果您有一个函数需要：
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）是衡量任何代码运行时性能的多项式时间复杂度之一。
我希望你已经听说过二进制搜索算法。
假设您必须在大小为N的数组中找到一个元素。
基本上，代码执行如下N不适用于2不适用于4N/8…等
如果你把每一级所做的所有工作相加，你将得到n（1+1/2+1/4….），等于O（logn）
我一直以来在脑海中想象运行在O（log n）中的算法的最佳方式如下：
如果您将问题大小增加一个乘法量（即将其大小乘以10），则做功仅增加一个加法量。
将此应用于二叉树问题，这样您就有了一个很好的应用程序：如果将二叉树中的节点数加倍，则高度仅增加1（一个加法量）。如果再增加一倍，它仍然只增加了1。（显然，我假设它保持平衡）。这样，当问题规模成倍增加时，你的工作量不会加倍，而只是做了稍微多一点的工作。这就是为什么O（logn）算法非常棒的原因。
对数运行时间（O（log n））本质上意味着运行时间与输入大小的对数成比例增长-例如，如果10个项目最多需要一定的时间x，100个项目最多花费2倍，10000个项目最多耗费4倍，那么它看起来像是O（log n）时间复杂性。
但O（log n）到底是什么？例如，如果一个>完整二叉树的高度是O（logn），这意味着什么？
我会将其重新表述为“完整二叉树的高度是logn”。如果一步一步向下遍历，计算完整的二叉树的高度将是O（logn）。
我无法理解如何用对数来识别函数时间
对数本质上是幂的倒数。因此，如果函数的每个“步骤”都在从原始项集中删除一个元素因子，那就是对数时间算法。
对于树的示例，您可以很容易地看到，当您继续遍历时，逐步降低节点级别会减少指数级的元素数量。浏览按姓名排序的电话簿的流行示例基本上等同于遍历二进制搜索树（中间页面是根元素，您可以在每个步骤中推断是向左还是向右）。
