我正在学习大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（logn）有点误导，更准确地说，它是O（log2n），即（以2为底的对数）。
平衡二叉树的高度是O（log2n），因为每个节点都有两个（注意log2n中的“两个”）子节点。因此，具有n个节点的树的高度为log2n。
另一个例子是二进制搜索，它的运行时间为O（log2n），因为在每一步中，您都将搜索空间除以2。
其他回答
但O（log n）到底是什么？例如，如果一个>完整二叉树的高度是O（logn），这意味着什么？
我会将其重新表述为“完整二叉树的高度是logn”。如果一步一步向下遍历，计算完整的二叉树的高度将是O（logn）。
我无法理解如何用对数来识别函数时间
对数本质上是幂的倒数。因此，如果函数的每个“步骤”都在从原始项集中删除一个元素因子，那就是对数时间算法。
对于树的示例，您可以很容易地看到，当您继续遍历时，逐步降低节点级别会减少指数级的元素数量。浏览按姓名排序的电话簿的流行示例基本上等同于遍历二进制搜索树（中间页面是根元素，您可以在每个步骤中推断是向左还是向右）。
分而治之范式中的算法具有复杂性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/2的问题空间。但二进制搜索并不是唯一的例子。假设，你以某种方式证明了，在每一步中，你至少丢掉了1/128的问题空间。这意味着，您的程序仍然以O（logN）时间运行，尽管比二进制搜索慢得多。这是分析递归算法的一个很好的提示。通常可以证明，在每一步递归都不会使用几个变量，这会导致问题空间中某些分数的截断。
这两种情况需要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);
}
