我正在学习大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（log n）到底是什么？例如，如果一个>完整二叉树的高度是O（logn），这意味着什么？
我会将其重新表述为“完整二叉树的高度是logn”。如果一步一步向下遍历，计算完整的二叉树的高度将是O（logn）。
我无法理解如何用对数来识别函数时间
对数本质上是幂的倒数。因此，如果函数的每个“步骤”都在从原始项集中删除一个元素因子，那就是对数时间算法。
对于树的示例，您可以很容易地看到，当您继续遍历时，逐步降低节点级别会减少指数级的元素数量。浏览按姓名排序的电话簿的流行示例基本上等同于遍历二进制搜索树（中间页面是根元素，您可以在每个步骤中推断是向左还是向右）。
其他回答
这仅仅意味着该任务所需的时间随着log（n）的增加而增加（例如：n＝10时为2s，n＝100时为4s，…）。请阅读维基百科关于二进制搜索算法和大O符号的文章以了解更多的精度。
我可以举一个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是常数）。
logx到基b=y是b^y=x的倒数
如果有深度为d、大小为n的M元树，则：
遍历整棵树~O（M^d）=O（n）在树中行走一条路径~O（d）=O（logn到基M）
我想补充一点，树的高度是从根到叶的最长路径的长度，节点的高度是该节点到叶的最大路径的长度。路径表示在两个节点之间遍历树时遇到的节点数。为了实现O（logn）时间复杂度，树应该是平衡的，这意味着任何节点的子节点之间的高度差应该小于或等于1。因此，树并不总是保证时间复杂度O（log n），除非它们是平衡的。实际上，在某些情况下，在最坏情况下，树中搜索的时间复杂度可能为O（n）。
你可以看看平衡树，比如AVL树。这项工作是在插入数据时平衡树，以便在树中搜索时保持（logn）的时间复杂度。
对数
好的，让我们试着完全理解对数到底是什么。
想象一下，我们有一根绳子，把它拴在一匹马身上。如果绳子直接系在马身上，那么马拉离（例如，从人身上）所需的力直接为1。
现在想象绳子绕在一根杆子上。要想脱身的马现在必须用力拉很多倍。次数取决于绳索的粗糙度和杆的大小，但我们假设它会将一个人的力量乘以10（当绳索完全转弯时）。
现在，如果绳子绕一圈，马需要用力拉10倍。如果人类决定让马变得很困难，他可以再次将绳子绕在一根杆子上，使它的力量增加10倍。第三个循环将再次将强度增加10倍。
我们可以看到，对于每个循环，值增加10。获得任何数字所需的圈数称为数字的对数，即我们需要3个柱将你的力量乘以1000倍，需要6个柱将力量乘以1000000。
3是1000的对数，6是1000000的对数（以10为底）。
那么O（log n）实际上是什么意思？
在上面的例子中，我们的“增长率”是O（logn）。每增加一圈，我们的绳子所能承受的力就会增加10倍：
Turns | Max Force
0 | 1
1 | 10
2 | 100
3 | 1000
4 | 10000
n | 10^n
现在上面的例子确实使用了基数10，但幸运的是，当我们讨论大o符号时，对数的基数是微不足道的。
现在，让我们假设您正在尝试猜测1-100之间的数字。
Your Friend: Guess my number between 1-100!
Your Guess: 50
Your Friend: Lower!
Your Guess: 25
Your Friend: Lower!
Your Guess: 13
Your Friend: Higher!
Your Guess: 19
Your Friend: Higher!
Your Friend: 22
Your Guess: Lower!
Your Guess: 20
Your Friend: Higher!
Your Guess: 21
Your Friend: YOU GOT IT!
现在你猜了7次才猜对。但这里的关系是什么？你可以从每一个额外的猜测中猜出最多的项目是什么？
Guesses | Items
1 | 2
2 | 4
3 | 8
4 | 16
5 | 32
6 | 64
7 | 128
10 | 1024
使用该图，我们可以看到，如果我们使用二进制搜索来猜测1-100之间的数字，最多需要7次尝试。如果我们有128个数字，我们也可以在7次尝试中猜出数字，但129个数字最多需要8次尝试（与对数相关，这里我们需要7次猜测128个值范围，10次猜测1024个值范围。7是128的对数，10是1024的对数（以2为底））。
注意，我用粗体字“最多”。大O符号总是指更坏的情况。如果你运气好，你可以一次猜出数字，所以最好的情况是O（1），但那是另一回事。
我们可以看到，我们的数据集正在缩小。识别算法是否具有对数时间的一个很好的经验法则是查看数据集在每次迭代后是否按一定顺序收缩
O（n log n）呢？
你最终会遇到一个线性时间O（n log（n））算法。上述经验法则再次适用，但这一次对数函数必须运行n次，例如，将列表的大小减少n次，这在合并排序等算法中发生。
您可以很容易地确定算法时间是否为n log n。寻找一个在列表（O（n））中迭代的外部循环。然后查看是否存在内部循环。如果内部循环在每次迭代时都在切割/减少数据集，则该循环为（O（logn）），因此整个算法为=O（n logn）。
免责声明：绳对数示例摘自W.Sawyer的《数学家的喜悦》一书。
