我正在学习大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，但我不知道如何识别具有对数时间的函数。
当前回答
这仅仅意味着该任务所需的时间随着log（n）的增加而增加（例如：n＝10时为2s，n＝100时为4s，…）。请阅读维基百科关于二进制搜索算法和大O符号的文章以了解更多的精度。
其他回答
O（logn）指的是一个函数（或算法，或算法中的步骤），其工作时间与输入大小的对数成正比（大多数情况下通常以2为基数，但并不总是以2为底，在任何情况下，通过big-O符号*，这都是无关紧要的）。
对数函数是指数函数的倒数。换句话说，如果您的输入呈指数增长（而不是通常认为的线性增长），则函数呈线性增长。
O（logn）运行时间在任何一种分而治之的应用程序中都很常见，因为（理想情况下）每次都会将工作减半。如果在每一个除法或征服步骤中，你都在做恒定时间的工作（或不是恒定时间的，但随着时间的增长比O（log n）慢），那么你的整个函数就是O（log）。相当常见的是，每个步骤都需要输入线性时间；这将相当于O（n log n）的总时间复杂度。
二进制搜索的运行时间复杂性是O（logn）的一个例子。这是因为在二进制搜索中，通过将数组分成两半，并且每一步只关注一半，您总是忽略后面每一步的一半输入。每一步都是恒定的时间，因为在二进制搜索中，您只需要将一个元素与关键字进行比较，就可以确定下一步要做什么，而不管您考虑的数组在任何时候都有多大。因此，大约执行log（n）/log（2）步。
合并排序的运行时间复杂性是O（n log n）的一个例子。这是因为每一步都将阵列一分为二，总共约为log（n）/log（2）步。然而，在每一步中，您都需要对所有元素执行合并操作（无论是对n/2个元素的两个子列表执行一次合并操作，还是对n/4个元素的四个子列表执行两次合并操作都是无关紧要的，因为这增加了每一步对n个元素执行合并的必要性）。因此，总复杂度为O（n log n）。
*记住，根据定义，big-O表示法并不重要。同样，通过改变对数的基数规则，不同基数的对数之间的唯一差异是一个常数因子。
对数运行时间（O（log n））本质上意味着运行时间与输入大小的对数成比例增长-例如，如果10个项目最多需要一定的时间x，100个项目最多花费2倍，10000个项目最多耗费4倍，那么它看起来像是O（log n）时间复杂性。
这两种情况需要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);
}
我想补充一点，树的高度是从根到叶的最长路径的长度，节点的高度是该节点到叶的最大路径的长度。路径表示在两个节点之间遍历树时遇到的节点数。为了实现O（logn）时间复杂度，树应该是平衡的，这意味着任何节点的子节点之间的高度差应该小于或等于1。因此，树并不总是保证时间复杂度O（log n），除非它们是平衡的。实际上，在某些情况下，在最坏情况下，树中搜索的时间复杂度可能为O（n）。
你可以看看平衡树，比如AVL树。这项工作是在插入数据时平衡树，以便在树中搜索时保持（logn）的时间复杂度。
O（logn）是衡量任何代码运行时性能的多项式时间复杂度之一。
我希望你已经听说过二进制搜索算法。
假设您必须在大小为N的数组中找到一个元素。
基本上，代码执行如下N不适用于2不适用于4N/8…等
如果你把每一级所做的所有工作相加，你将得到n（1+1/2+1/4….），等于O（logn）
