我有一个排序的 double 组(实际上是纬度)，它们相对均匀地分布在 -10 到 -43 的范围内。现在，如果我对该列表进行二分搜索，我会得到 O(log N)。
但是，我可以通过查找表进一步优化，查找表中有 34 个键(-10 到 -43)，然后可以直接跳转到该数字的起点。
例如:-23.123424 首先查找键 23 并知道所有 -23 值的开始和结束范围。然后我可以从中间进行二进制搜索。
我的 Big-O 会是什么样子？
最佳答案
它仍然是 O(log n)。考虑一下:在整数查找表中查找起始索引需要花费恒定的时间，因此该部分不会添加任何内容。然后是 O(log n) 进行二分查找。实际上，它大约需要 log n/34，因为您希望搜索一个平均小 34 倍的数组(这些值分布在 34 个不同的区间，边界从 -43 到 -10)，但是在 big 中不考虑常量乘数-O 符号。
关于big-o - 什么大 O 方程描述了我的搜索？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9815828/