我正在学习大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，但我不知道如何识别具有对数时间的函数。
当前回答
实际上，如果您有一个n个元素的列表，并从该列表中创建一个二叉树（就像在除法和征服算法中一样），您将一直除以2，直到达到大小为1的列表（树叶）。
在第一步，你除以2。然后，您有2个列表（2^1），将每个列表除以2，因此您有4个列表（2*2），然后再进行一次除法，您有8个列表（3^3），依此类推，直到列表大小为1
这给出了一个等式：
n/（2^步）=1<=>n=2^步<=>lg（n）=步
（取每边的lg，lg为对数基数2）
其他回答
分治算法通常具有运行时间的logn成分。这来自于输入的重复减半。
在二进制搜索的情况下，每次迭代都会丢弃一半的输入。需要注意的是，在Big-O表示法中，log是以2为底的log。
编辑：如上所述，对数基数并不重要，但当推导算法的Big-O性能时，对数因子将来自减半，因此我认为它是基数2。
每次编写算法或代码时，我们都会尝试分析其渐近复杂性。它不同于它的时间复杂性。
渐近复杂度是算法执行时间的行为，而时间复杂度是实际执行时间。但有些人可以互换使用这些术语。
因为时间复杂度取决于各种参数。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
随着输入大小的增加，所做的工作也会增加，并且与任何机器无关。如果你试图找出工作单位的价值它实际上取决于上述参数。它会根据系统和所有参数而改变。
O（logN）基本上意味着时间线性上升，而N指数上升。因此，如果计算10个元素需要1秒，则计算100个元素需要2秒，计算1000个元素需要3秒，依此类推。
当我们进行分而治之的算法（如二进制搜索）时，它是O（logn）。另一个例子是快速排序，每次我们将数组分成两部分，每次都需要O（N）时间才能找到一个枢轴元素。因此，N O（log N）
logb（n）是什么？
它是指在达到尺寸为1的截面之前，可以将长度为n的原木重复切成b等份的次数。
在信息技术中，它意味着：
f(n)=O(g(n)) If there is suitable constant C and N0 independent on N,
such that
for all N>N0 "C*g(n) > f(n) > 0" is true.
看来这个符号主要是从数学中提取出来的。
本文引用了一句话：D.E.Knuth，《大OMICRON、大OMEGA和大THETA》，1976年：
基于这里讨论的问题，我建议SIGACT以及计算机科学和数学期刊的编辑，采用上面定义的符号，除非有更好的替代方案很快就会发现。
今天是2016年，但我们今天仍然使用它。
在数学分析中，这意味着：
lim (f(n)/g(n))=Constant; where n goes to +infinity
但即使在数学分析中，有时这个符号也用于表示“C*g（n）>f（n）>0”。
我从大学里就知道，这个符号是由德国数学家朗道（1877-1938）创造的
