假设我有一个未排序的实数数组，长度为 N . 我想找到最大的非正数 y ，然后在数组中找到小于 y 的第一个数字 x ，并且第一个数字 z 大于 y .
我想理论上将顺序搜索与二进制搜索非渐近地比较（即不仅仅是用大的Os）来找到这些值 . 陈述是否合理：
-
顺序搜索需要
-
0排序比较， -
3*N搜索比较（三次连续搜索） . -
二进制搜索需要
-
2*N*ln(N) ≈ 1.39*N*log_2(N)排序比较（quicksort, average）， -
高达
log_2(N)搜索比较（只有一次搜索，因为数组已排序，因此我们可以查看排序数组中的相邻值，找到x和z一旦找到y） .
因此，我可以说如果二进制搜索会更快
1.39*N*log_2(N) + log_2(N) < 3*N
<=>
0 < N < 3.44779
即仅适用于极小的阵列？
2 回答
是的，你的结论是正确的 . 但是，通常使用排序数组（或任何其他有组织的结构）的意义在于，只执行一次或很少执行预处理步骤 - 与频繁查询相反 . 经过多次查询后，预处理成本得到了回报 .
不，由于几个原因，这不是一个有效的结论 .
您只考虑比较的成本（这是次要的），而不是分支和掉期的成本 .
您正在使用由quicksort执行的平均比较次数的近似值，该比率仅是渐近有效的 .
你're using 2705419 as a stand-in for 2705420 . Real processors do not take a constant time to execute a given operation, and the total time they spend on a procedure is not the sum of each operation'的执行时间 .