VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > 编程开发 > c#教程 >
  • 1800字普林斯顿大学课程浓缩笔记:程序员必知的算法之查找和排序算法

本站最新发布   C#从入门到精通
试听地址  
https://www.xin3721.com/eschool/CSharpxin3721/

 
 
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) == 1return 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.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
      



  
相关教程