输入的平方根是否位于该输入的中间？

Question

我开始阅读《竞争程序员手册》，在第 20 页，作者写了有关不同算法复杂性类别的文章。在覆盖 √𝑛 时，他写道：

O(√𝑛) 平方根算法比 O(log𝑛) 慢，但比 O(𝑛) 快。

平方根的一个特殊属性是 √𝑛 = 𝑛/√𝑛，因此平方根 √𝑛 在某种意义上位于输入的中间。

我不太确定他所说的输入中间是什么意思；他只是说 √𝑛 正好位于范围 [1, 𝑛] 之间吗？如果是这样的话，log𝑛 满足相同的属性，我不明白为什么它值得注意。

log𝑛 = O(√𝑛) 和 √𝑛 = O(𝑛)，所以很明显 O(√𝑛) 位于这两个其他明确定义的类别之间，但我想知道是否有人了解“中间”是什么输入的”应该是在这种情况下的意思。

Answer 1

几何

中间，即当 1 和 𝑛 是几何序列中的第一项和第三项时，则 √𝑛 是第二个（“中间”）项。 一个示例是将具有 𝑛 元素的输入数组划分为 √𝑛 存储桶。由于平方根的这种“特殊”属性，这些桶将分别具有大约 √𝑛 元素。例如参见

跳转搜索

。