当前位置:
首页 > Python基础教程 >
-
1800字普林斯顿大学课程浓缩笔记:程序员必知的算法之查找和排序算法
在这一章节,考虑经典的算法:查找和排序,以及具体的应用。
老生常谈,偶尔遇到阐述这两类问题相关的极好素材,它们结合示意图,言简意赅,清晰明了。故分享出来。
二分查找还是相对容易理解的,我们的目标是准确无误地写出其代码。为此先从原理理解透二分查找,在游戏 "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
栏目列表
最新更新
nodejs爬虫
Python正则表达式完全指南
爬取豆瓣Top250图书数据
shp 地图文件批量添加字段
爬虫小试牛刀(爬取学校通知公告)
【python基础】函数-初识函数
【python基础】函数-返回值
HTTP请求:requests模块基础使用必知必会
Python初学者友好丨详解参数传递类型
如何有效管理爬虫流量?
SQL SERVER中递归
2个场景实例讲解GaussDB(DWS)基表统计信息估
常用的 SQL Server 关键字及其含义
动手分析SQL Server中的事务中使用的锁
openGauss内核分析:SQL by pass & 经典执行
一招教你如何高效批量导入与更新数据
天天写SQL,这些神奇的特性你知道吗?
openGauss内核分析:执行计划生成
[IM002]Navicat ODBC驱动器管理器 未发现数据
初入Sql Server 之 存储过程的简单使用
这是目前我见过最好的跨域解决方案!
减少回流与重绘
减少回流与重绘
如何使用KrpanoToolJS在浏览器切图
performance.now() 与 Date.now() 对比
一款纯 JS 实现的轻量化图片编辑器
关于开发 VS Code 插件遇到的 workbench.scm.
前端设计模式——观察者模式
前端设计模式——中介者模式
创建型-原型模式