算法(4th ed)(60):基础——基础编程模型 3.10.4

阅读数:17 2019 年 10 月 30 日 07:09

算法(4th ed)(60):基础——基础编程模型 3.10.4

(二分查找:性能)

一个程序只是可用往往是不够的。例如,以下 rank() 的实现也可以很简单,它会检查数组的每个元素,甚至都不需要数组是有序的:

复制代码
public static int rank(int key, int[] a)
{
for (int i = 0; i < a.length; i++)
if (a[i] == key) return i;
return -1;
}

有了这个简单易懂的解决方案,我们为什么还需要归并排序和二分查找呢?你在完成练习 1.1.38 时会看到,计算机用 rank() 方法的暴力实现处理大量输入(比如含有 100 万个条目的白名单和 1000 万条交易)非常慢。没有如二分查找或者归并排序这样的高效算法,解决大规模的白名单问题是不可能的。良好的性能常常是极为重要的,因此我们会在 1.4 节中为性能研究做一些铺垫,并会分析我们学习的所有算法的性能特点(包括 2.2 节的归并排序和 3.1 节中的二分查找)。

目前,我们在这里粗略地勾勒出我们的编程模型的目标是,确保你能够在计算机上运行类似于 BinarySearch 的代码,使用它处理我们的测试数据并为适应各种情况修改它(比如本节练习中所描述的一些情况)以完全理解它的可应用性。我们的编程模型就是设计用来简化这些活动的,这对各种算法的学习至关重要。

评论

发布