我正在学习大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。
其他回答
如果你在图形计算器或类似的东西上绘制一个对数函数，你会发现它的上升速度非常慢——甚至比线性函数还要慢。
这就是为什么对数时间复杂度算法备受追捧的原因：即使对于真正大的n（例如，假设n＝10^8），它们的性能也超出了可接受的范围。
但O（log n）到底是什么？例如，如果一个>完整二叉树的高度是O（logn），这意味着什么？
我会将其重新表述为“完整二叉树的高度是logn”。如果一步一步向下遍历，计算完整的二叉树的高度将是O（logn）。
我无法理解如何用对数来识别函数时间
对数本质上是幂的倒数。因此，如果函数的每个“步骤”都在从原始项集中删除一个元素因子，那就是对数时间算法。
对于树的示例，您可以很容易地看到，当您继续遍历时，逐步降低节点级别会减少指数级的元素数量。浏览按姓名排序的电话簿的流行示例基本上等同于遍历二进制搜索树（中间页面是根元素，您可以在每个步骤中推断是向左还是向右）。
logb（n）是什么？
它是指在达到尺寸为1的截面之前，可以将长度为n的原木重复切成b等份的次数。
如果你正在寻找一个基于直觉的答案，我想为你提供两种解释。
想象一下一座很高的山，它的底部也很宽。要到达山顶，有两种方式：一种是一条围绕山顶螺旋延伸的专用通道，另一种是切割出的小露台状雕刻，以提供楼梯。现在，如果第一种方式在线性时间O（n）内到达，则第二种方式是O（logn）。想象一个算法，它接受整数n作为输入，并在时间上与n成比例地完成，那么它是O（n）或θ。
大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.
