use*_*383 0 algorithm tree binary-tree binary-search-tree data-structures
考虑这个二叉搜索树的例子。
n =10 ;and if base = 2 then
log n = log 2 (10) = 3.321928。
我假设这意味着搜索一个元素最多需要 3.321 步（访问）。我还假设 BST 是平衡二叉树。
现在要访问值为 25 的节点。我必须转到以下节点：
50
40
30
25
所以我必须访问4个节点。3.321 几乎等于 4。
这种理解是对还是错？
我认为你的理解不太正确。
\n\n大 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)。
因此，如果 forn=10花费了 4 个步骤，那么 forn=100应该花费大约两倍的时间，即 8 个步骤，因为log(100)/log(10)=2和 forn=10000应该花费 16 个步骤。
如果 forn=10需要 1000000 步，那么 forn=100需要 2000000 步，而n=10000\xe2\x80\x94 则需要 4000000 步。
这都是为了“足够大” n\xe2\x80\x94 对于小ns 步数可以偏离这个比例。对于大多数实用算法来说，“足够大”通常从 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常数会不同。