我正在学习大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），它们的性能也超出了可接受的范围。
我可以举一个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的数组中找到一个元素。
基本上，代码执行如下N不适用于2不适用于4N/8…等
如果你把每一级所做的所有工作相加，你将得到n（1+1/2+1/4….），等于O（logn）
每次编写算法或代码时，我们都会尝试分析其渐近复杂性。它不同于它的时间复杂性。
渐近复杂度是算法执行时间的行为，而时间复杂度是实际执行时间。但有些人可以互换使用这些术语。
因为时间复杂度取决于各种参数。1.物理系统2.编程语言3.编码样式4.还有更多。。。。。。
实际执行时间不是一个很好的分析指标。
相反，我们将输入大小作为参数，因为无论代码是什么，输入都是相同的。因此，执行时间是输入大小的函数。
以下是线性时间算法的示例
线性搜索给定n个输入元素，要搜索数组中的元素，最多需要“n”个比较。换句话说，无论你使用什么编程语言，你喜欢什么编码风格，在什么系统上执行它。在最坏的情况下，它只需要n次比较。执行时间与输入大小成线性比例。
它不仅仅是搜索，无论是什么工作（增量、比较或任何操作），它都是输入大小的函数。
所以当你说任何算法都是O（logn）这意味着执行时间是输入大小n的log倍。
随着输入大小的增加，完成的工作（这里是执行时间）增加。（因此，比例）
n Work
2 1 units of work
4 2 units of work
8 3 units of work
随着输入大小的增加，所做的工作也会增加，并且与任何机器无关。如果你试图找出工作单位的价值它实际上取决于上述参数。它会根据系统和所有参数而改变。
下面的解释是使用完全平衡的二叉树来帮助您理解我们如何获得对数时间复杂度。
二叉树是一种情况，其中大小为n的问题被划分为大小为n/2的子问题，直到我们达到大小为1的问题：
这就是你如何得到O（logn），这是在上面的树上需要完成的工作量，以获得解决方案。
具有O（logn）时间复杂度的常见算法是二进制搜索，其递归关系为T（n/2）+O（1），即在树的每个后续级别上，您将问题分成一半，并执行恒定数量的额外工作。
