-
C#教程之1800字普林斯顿大学课程浓缩笔记:程序员必知的算法之查找和排序算法
本站最新发布 C#从入门到精通
试听地址 https://www.xin3721.com/eschool/CSharpxin3721/
1 两类经典算法
2 猜数字游戏
3 分析二分查找
试听地址 https://www.xin3721.com/eschool/CSharpxin3721/
在这一章节,考虑经典的算法:查找和排序,以及具体的应用。
老生常谈,偶尔遇到阐述这两类问题相关的极好素材,它们结合示意图,言简意赅,清晰明了。故分享出来。
二分查找还是相对容易理解的,我们的目标是准确无误地写出其代码。为此先从原理理解透二分查找,在游戏 "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.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
栏目列表
最新更新
C# 数据操作系列 - 17 Dapper ——号称可以与
C# 数据操作系列 - 18 让Dapper更强的插件
C#编码转换
python list遍历方法汇总
将Python分成7个阶段学习,你会发现学习
Python中的单例模式如何正确运用?本文详
使用Python爬虫的方式把自己喜欢的音乐的
pandas.cut使用总结
Python之Selenium如何正确运用?案例详解
Python爬虫是如何遍历文档树呢?一招教你
基于UDP的服务器端和客户端
再谈UDP和TCP
在socket编程中使用域名
网络数据传输时的大小端问题
socket编程实现文件传输功能
如何优雅地断开TCP连接?
图解TCP四次握手断开连接
详细分析TCP数据的传输过程
图解TCP数据报结构以及三次握手(非常详
TCP协议的粘包问题(数据的无边界性)
SqlServer 利用游标批量更新数据
BOS只读状态修改
SQL Server等待事件—PAGEIOLATCH_EX
数据库多行转换为单一列
获取数据表最后最后访问,修改,更新,
计算经历的时间
SQL查询结果自定义排序
修改数据库默认位置
日期简单加或减
从日期获取年,月或日