VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > Python基础教程 >

  • 1800字普林斯顿大学课程浓缩笔记：程序员必知的算法之查找和排序算法

 
 
1 两类经典算法
 
 

在这一章节，考虑经典的算法：查找和排序，以及具体的应用。

 

老生常谈，偶尔遇到阐述这两类问题相关的极好素材，它们结合示意图，言简意赅，清晰明了。故分享出来。

 

 
 
2 猜数字游戏
 
 

二分查找还是相对容易理解的，我们的目标是准确无误地写出其代码。为此先从原理理解透二分查找，在游戏 "20个问题"中，你的任务是猜出一个神秘的数字，它位于0~n-1共n个之内。

 

简化起见，我们假定n是偶数，问题的问答形式是这样：

Q: “我猜神秘数为 i”

A：“你猜的数字 i 大于或等于 真正的神秘数77”

 

这个过程，参考如下示意图：

 

 

此处，一个有效的策略是维护一个间隔，它包含 x ，猜的数位于这个区间中间，以下 Questions类实现了这个策略。

 

 1public class Questions {
 2
 3    // invariant: answer is in [lo, hi)
 4    public static int search(int lo, int hi) {
 5        if ((hi - lo) == 1) return lo;
 6        int mid = lo + (hi - lo) / 2;
 7        StdOut.printf("Is it less than %d?  ", mid);
 8        if (StdIn.readBoolean()) 
 9            return search(lo, mid);
10        else                     
11            return search(mid, hi);
12    }
13
14    public static void main(String[] args) {
15        int k = Integer.parseInt(args[0]);
16        int n = (int) Math.pow(2, k);
17        StdOut.printf("Think of an integer between %d and %d\n", 0, n-1);
18        int secret = search(0, n);
19        StdOut.printf("Your number is %d\n", secret);
20    }
21
22}

 

这里面有个细节，mid = lo + (hi-lo)/2，这样写是为了防止发生溢出。

 

这个猜数字的游戏就是二叉搜索的一个经典例子。

 

 
 
3 分析二分查找
 
 

3.1 时间复杂度 

在上面这个猜谜游戏中，使用了二分查找，因为没迭代一次，求解区间减为原来一半，因此二分查找的时间复杂度为 lgn.

 

3.2 二分查找退化为线性搜索 

如果我们不采取上面的猜数字策略，依次1,2,3,...n-1，直到命中数字，这就是 brute-force 暴力算法，此时的时间复杂度为 n.

 

3.3 二进制表示  

某个数转化为二进制表示(代码见下)的过程与二分查找很相似，例如，神秘数为77，然后猜题的回答为：no yes yes no no yes no ，则二进制表示为 1001101，二进制表示恰好为 77.

 

 1public class Binary { 
 2    public static void main(String[] args) { 
 3
 4        // read in the command-line argument
 5        int n = Integer.parseInt(args[0]);
 6
 7        // set power to the largest power of 2 that is <= n
 8        int power = 1;
 9        while (power <= n/2) {
10            power *= 2;
11        }
12
13        // check for presence of powers of 2 in n, from largest to smallest
14        while (power > 0) {
15
16            // power is not present in n 
17            if (n < power) {
18                System.out.print(0