algorithm - 比较顺序搜索和二分搜索

Question

假设我有一个未排序的实数数组，长度为N。我想找到最大的非正数y，然后是数组中x小于的第一个数，以及大于的第一个数。yzy

我想在理论上将顺序搜索与二进制搜索进行非渐近比较（即不仅仅是使用大 Os）以找到这些值。是否合理地陈述：

• 顺序搜索需要
  • 0排序比较，
  • 3*N搜索比较（三个顺序搜索）。
• 二分查找需要
  • 2*N*ln(N) ≈ 1.39*N*log_2(N)排序比较（快速排序，平均），
  • 直到log_2(N)比较搜索（只有一次搜索，因为数组是排序的，因此我们可以查看排序数组中的相邻值来查找x，z一旦我们找到y）。

因此，我可以说二分查找会更快吗？

1.39*N*log_2(N) + log_2(N) < 3*N 
<=> 
0 < N < 3.44779

即仅适用于极小的阵列？

Answer 1

是的，你的结论是正确的。但是，通常使用排序数组（或任何其他有组织的结构）的目的是只执行一次或很少执行预处理步骤 - 与频繁查询相反。经过多次查询，预处理成本得到了回报。

Answer 2

不，这不是一个有效的结论，有几个原因。

• 您只考虑比较的成本（这是次要的），而不是分支和交换的成本。
• 您正在使用快速排序执行的平均比较次数的近似值，该近似值仅渐近有效。
• 您正在使用“操作次数”作为“速度”的替代品。真正的处理器执行给定操作的时间不是固定的，而且它们花在一个过程上的总时间不是每个操作执行时间的总和。