O（log n）的复杂性是什么意思？
What is meant by complexity of O(log n)?
考虑 this 二叉搜索树的例子。
n =10 ;and if base = 2 then
log n = log2(10) = 3.321928.
我假设这意味着最多需要 3.321 步（访问）来搜索一个元素。我还假设 BST 是平衡二叉树。
现在访问值为 25 的节点。我必须去以下节点：
50
40
30
25
所以我不得不访问 4 个节点。 3.321 几乎等于 4。
这个理解对还是错？
您的想法不完全正确。考虑的 steps/accesses 用于比较。但是，O(log n)只是一个衡量渐近复杂度的参数，而不是精确的步骤计算。正如 Petr 所准确回答的那样，您应该仔细阅读他的回答中提到的要点。
此外，BST 是二叉搜索树，有时也称为有序或排序的二叉树。
Exact 运行 time/comparisons 无法从渐近复杂性度量中导出。为此，您必须 return 精确推导在 BST 中搜索元素。
假设我们有一棵具有 n 个节点的“平衡”树。如果找到一个条目的最大比较次数是 (k+1)，其中 k 是高度，我们有
2^(k+1) - 1 = n
我们从中得到
k = log2(n+1) – 1 = O(log2n).
如您所见，在最坏情况分析中测量渐近复杂性时，还有其他常数因子被删除。因此，比较的复杂性降低到 O(log2n).
接下来，演示如何根据比较的方式在 BST 中搜索元素：-
1. Selecting 50,if root element //compare and move below for left-child or right-child
2. Movement downwards from 50 to 40, the leftmost child
3. Movement downwards from 40 to 30, the leftmost child
4. Movement downwards from 30 to 25, found and hence no movement further.
// Had there been more elements to traverse deeper, it would have been counted the 5th step.
因此，经过3次迭代向下遍历，找到了第25条。所以，有4次比较和3次向下遍历（因为高度是3）。
通常你会这样说:-
Given a balanced binary search tree with n elements, you need O(log n) operations to search.
或
Search in a balanced binary search tree of n elements is in O(log n).
我更喜欢第二个短语，因为它强调了O是一个返回给定x（简称O(x)）的一组函数的函数。 x: N → N 是一个函数。 x的输入是一个函数输入的大小，x的输出可以理解为你需要的运算次数。
函数 g 在 O(x) 中，当 g 低于 x 乘以任意非负常数 从某个开始点 n_0 所有后续 n.
在计算机科学中，g 经常被设置为等于错误的算法。给定输入大小，它可能是算法的操作次数。请注意，这是不同的东西。
更正式地说：
因此，关于您的问题：您必须定义 n 是什么（概念上，不是数字）。在您的示例中，它最终是节点数或到叶的最长路径上的节点数。
通常，当您使用 Big-O 表示法时，您对 "average" 情况不感兴趣（尤其是对某些给定情况不感兴趣），但您想说说最坏的情况。
我认为你的理解不太正确。
big-O 表示法没有说明完成的确切步骤数。符号 O(log n) 表示某物与 log n 大致成正比，但不一定相等。
如果你说在 BST 中搜索一个值的步骤数是 O(log n)，这意味着它大约是 C*log n 对于一些常数 C 不依赖于n，但它没有说明 C 的值。所以对于 n=10 这从来没有说步数是 4 或其他。它可以是 1，也可以是 1000000，这取决于 C 是什么。
这个表示法说的是，如果您考虑两个大小不同且足够大的示例，比如 n1 和 n2，那么这两个示例中的步数大约为 log(n1)/log(n2).
因此，如果 n=10 需要您，比方说，4 步，那么 n=100 则需要大约两倍的时间，即 8 步，因为 log(100)/log(10)=2， n=10000 需要 16 个步骤。
如果 n=10 需要 1000000 步，那么 n=100 需要 2000000 步，n=10000 需要 4000000 步。
这就是 "large enough" n — 对于小的 ns，步数可能会偏离这个比例。对于大多数实用算法，"large enough" 通常从 5-10 开始，如果不是 1，但从严格的角度来看，大 O 表示法对比例何时开始没有设置任何要求。
实际上 O(log n) 符号并不要求步数增长与 log n 成比例，但要求步数增长 不快 而不是与log n成比例，即步数的比例不应该是log(n1)/log(n2)，而是<=log(n1)/log(n2)。
另请注意另一种情况，可以使 O 表示法的背景更加清晰。不要考虑步数，而是要考虑在 BST 中搜索所花费的 时间。您显然无法预测这个时间，因为它取决于您 运行 所在的机器，取决于算法的特定实现，毕竟取决于您使用的时间单位（秒或纳秒等）。所以时间可以是 0.0001 或 100000 或其他。然而，所有这些影响（机器的速度等）都会通过一些常数因子粗暴地改变所有的测量结果。因此你可以说时间是O(log n)，只是在不同的情况下C常数会不同。
考虑 this 二叉搜索树的例子。
n =10 ;and if base = 2 then
log n = log2(10) = 3.321928.
我假设这意味着最多需要 3.321 步（访问）来搜索一个元素。我还假设 BST 是平衡二叉树。
现在访问值为 25 的节点。我必须去以下节点：
50
40
30
25
所以我不得不访问 4 个节点。 3.321 几乎等于 4。
这个理解对还是错？
您的想法不完全正确。考虑的 steps/accesses 用于比较。但是，O(log n)只是一个衡量渐近复杂度的参数，而不是精确的步骤计算。正如 Petr 所准确回答的那样，您应该仔细阅读他的回答中提到的要点。
此外，BST 是二叉搜索树，有时也称为有序或排序的二叉树。
Exact 运行 time/comparisons 无法从渐近复杂性度量中导出。为此，您必须 return 精确推导在 BST 中搜索元素。
假设我们有一棵具有 n 个节点的“平衡”树。如果找到一个条目的最大比较次数是 (k+1)，其中 k 是高度，我们有
2^(k+1) - 1 = n
我们从中得到
k = log2(n+1) – 1 = O(log2n).
如您所见，在最坏情况分析中测量渐近复杂性时，还有其他常数因子被删除。因此，比较的复杂性降低到 O(log2n).
接下来，演示如何根据比较的方式在 BST 中搜索元素：-
1. Selecting 50,if root element //compare and move below for left-child or right-child
2. Movement downwards from 50 to 40, the leftmost child
3. Movement downwards from 40 to 30, the leftmost child
4. Movement downwards from 30 to 25, found and hence no movement further.
// Had there been more elements to traverse deeper, it would have been counted the 5th step.
因此，经过3次迭代向下遍历，找到了第25条。所以，有4次比较和3次向下遍历（因为高度是3）。
通常你会这样说:-
Given a balanced binary search tree with n elements, you need O(log n) operations to search.
或
Search in a balanced binary search tree of n elements is in O(log n).
我更喜欢第二个短语，因为它强调了O是一个返回给定x（简称O(x)）的一组函数的函数。 x: N → N 是一个函数。 x的输入是一个函数输入的大小，x的输出可以理解为你需要的运算次数。
函数 g 在 O(x) 中，当 g 低于 x 乘以任意非负常数 从某个开始点 n_0 所有后续 n.
在计算机科学中，g 经常被设置为等于错误的算法。给定输入大小，它可能是算法的操作次数。请注意，这是不同的东西。
更正式地说：
因此，关于您的问题：您必须定义 n 是什么（概念上，不是数字）。在您的示例中，它最终是节点数或到叶的最长路径上的节点数。
通常，当您使用 Big-O 表示法时，您对 "average" 情况不感兴趣（尤其是对某些给定情况不感兴趣），但您想说说最坏的情况。
我认为你的理解不太正确。
big-O 表示法没有说明完成的确切步骤数。符号 O(log n) 表示某物与 log n 大致成正比，但不一定相等。
如果你说在 BST 中搜索一个值的步骤数是 O(log n)，这意味着它大约是 C*log n 对于一些常数 C 不依赖于n，但它没有说明 C 的值。所以对于 n=10 这从来没有说步数是 4 或其他。它可以是 1，也可以是 1000000，这取决于 C 是什么。
这个表示法说的是，如果您考虑两个大小不同且足够大的示例，比如 n1 和 n2，那么这两个示例中的步数大约为 log(n1)/log(n2).
因此，如果 n=10 需要您，比方说，4 步，那么 n=100 则需要大约两倍的时间，即 8 步，因为 log(100)/log(10)=2， n=10000 需要 16 个步骤。
如果 n=10 需要 1000000 步，那么 n=100 需要 2000000 步，n=10000 需要 4000000 步。
这就是 "large enough" n — 对于小的 ns，步数可能会偏离这个比例。对于大多数实用算法，"large enough" 通常从 5-10 开始，如果不是 1，但从严格的角度来看，大 O 表示法对比例何时开始没有设置任何要求。
实际上 O(log n) 符号并不要求步数增长与 log n 成比例，但要求步数增长 不快 而不是与log n成比例，即步数的比例不应该是log(n1)/log(n2)，而是<=log(n1)/log(n2)。
另请注意另一种情况，可以使 O 表示法的背景更加清晰。不要考虑步数，而是要考虑在 BST 中搜索所花费的 时间。您显然无法预测这个时间，因为它取决于您 运行 所在的机器，取决于算法的特定实现，毕竟取决于您使用的时间单位（秒或纳秒等）。所以时间可以是 0.0001 或 100000 或其他。然而，所有这些影响（机器的速度等）都会通过一些常数因子粗暴地改变所有的测量结果。因此你可以说时间是O(log n)，只是在不同的情况下C常数会不同。