-内存和查找 Lecture 10 - Memory and Search

官官方信息技术老师·13 页·深入（追求细节与边界）·0 次浏览·3 天前
✦ -内存和查找 Lecture 10 - Memory and Search信息技术-内存和查找 Lecture 10 -Hashing
内存层级查找算法复杂度数据结构

-内存和查找 Lecture 10 -

看懂内存层级如何决定不同查找算法的实际速度

按 空格/→ 演示下一步

1 / 13 页

全部页面点击任意一页，跳回舞台从这页播放

内存层级查找算法复杂度数据结构

-内存和查找 Lecture 10 -

看懂内存层级如何决定不同查找算法的实际速度

1第 1 页 · -内存和查找 Lecture 10 -

Lecture 10 Introduction

你在手机相册翻一张旧照片，几秒就出；但同样的查找放在备份硬盘里可能要等几分钟。差距从哪来？——不是算法不够聪明，而是数据所在的「物理位置」决定了成本。

内存层次
寄存器→L1/L2/L3→主存→SSD→HDD，每级延迟差 1~3 个数量级
查找代价模型
真实时间 ≈ 算法步数 × 每步内存访问成本，两者必须同时看
局部性原理
时间局部性（刚访问的还会再访）+ 空间局部性（访问附近数据），决定缓存命中率
时空权衡
哈希用 O(n) 空间换 O(1) 查找；排序+二分省空间换 O(log n)
图书馆找书对应 →内存层次中的查找

桌上=缓存（秒到）、阅览室=主存（几步路）、书库=磁盘（要上楼调档）

2第 2 页 · Lecture 10 Introduction

Search Algorithms

Search Algorithms：定义、要点与典型应用

Search Algorithms
Search Algorithms：定义、要点与典型应用
3第 3 页 · Search Algorithms

Binary Search

上页我们看到二分查找是搜索家族里最快的成员。但它的快有代价——它有一条硬性前提，也藏着微妙的实现陷阱。今天我们把它彻底拆开看。

有序前提
序列必须已排序；不满足则结果不可信
分治策略
取中点比较，每次排除一半候选
对数复杂度
n 经 ⌈log₂n⌉ 次减半即可归 1，时间 O(log n)
实现陷阱
mid 用 left+(right-left)/2 防溢出；边界 off-by-one 易错
典型变体
首末次出现、lower/upper_bound、旋转有序数组
猜数字游戏 1-100对应 →二分查找

每次猜中点，根据'大了/小了'砍掉一半可能

mid=left+right−left2\text{mid} = \text{left} + \frac{\text{right} - \text{left}}{2}
4第 4 页 · Binary Search

Selection Sort

查找告诉我们「数据在哪」，排序则解决「数据怎么排」。我们从最直观的排序算法开始——选择排序。

基本思路
反复从未排序部分挑出最小元素，放到已排序末尾
时间复杂度
最好最坏都是 O(n²)，比较次数恒为 n(n-1)/2
空间复杂度
O(1) 原地排序，仅需常数额外空间
最少交换
每轮只交换一次，总交换次数最多 n-1 次
不稳定性
基础实现不稳定，相等值的相对顺序会被打乱
整理一摞凌乱的扑克牌对应 →选择排序

每次扫一遍所有牌，把最小的抽出来放到手牌最左；剩下牌里再找最小，继续放左

C(n)=∑i=1n−1i=n(n−1)2C(n) = \sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}
5第 5 页 · Selection Sort

Selection Sort Demo

上一页我们说选择排序的本质是「每轮挑一个最小值归位」。但挑是怎么挑的？归又是怎么归的？这页我们用动画把它拆开看。

分区
维护"已排好前缀"和"未排后缀"的边界，每轮开始时边界指着本轮目标位置
扫描找最值
在未排序区从头到尾逐一比较，记录当前最小（或最大）元素的下标
交换归位
把最值与边界处元素做一次交换，本轮结束，边界右移一位
比较次数固定
无论输入是否已有序，每轮都扫一遍未排序区，总比较次数恒为 n(n-1)/2
老师按身高排队对应 →选择排序

每轮扫一遍剩余同学找最矮的，拎到当前空位，边界右推一位

$$T(n) = \frac{n(n-1)}{2} = O(n^2)$$
6第 6 页 · Selection Sort Demo

Another Selection Sort D

上一页我们用随机数组演示了选择排序。这次换个更有挑战的输入——含有重复元素的数组，看看会发生什么，以及它暴露出选择排序哪些深层的性质。

重复元素的尴尬
遇到值相同的元素，扫描找最小值时只看「值」，不区分它们原本的顺序，可能导致相等元素的相对位置被打乱
比较次数恒定
不管数组是否已经有序，每轮都要遍历未排序部分找最小值，比较次数固定为 n(n−1)/2
交换次数最少
每轮最多一次交换，总交换次数 ≤ n−1，比冒泡排序在写操作上友好得多
不稳定排序
默认实现把最小值与第一个位置交换，会破坏相等元素的相对顺序，属于不稳定排序算法
老师按身高排队对应 →选择排序扫描

每轮从剩余队伍里挑最矮的站到下一格；遇到两个一样高的，交换到前面时不保留谁先来的信息

比较次数=n(n−1)2\text{比较次数} = \frac{n(n-1)}{2}
7第 7 页 · Another Selection Sort D

Amortized Cost Analysis

Selection Sort 不管数据如何，每次都是 O(n²)。但有些操作偶尔极贵、大多数时候很便宜——比如动态数组扩容。这次需要新的衡量方式。

摊还成本
把偶尔昂贵操作的成本平摊到全部操作，得到每次操作的平均代价
为何需要
有的算法『平时便宜偶尔巨贵』，用最坏复杂度会严重高估真实开销
三种技巧
聚合：总开销÷操作数；记账：超额收费存信用；势能：定义势能函数
动态数组
满了就翻倍扩容：那次插入 O(n)，但摊还后所有插入都是 O(1)
非概率平均
摊还是确定性的最坏情况上界，不依赖输入分布的概率假设
房贷月供对应 →摊还成本

一次性大支出按月分摊，月供固定——关注每期平均价而非某次爆发性开销

8第 8 页 · Amortized Cost Analysis

Merge Sort

上页 Selection Sort 在最坏情况下是 O(n²)，n 一大就跑不动。Merge Sort 走出另一条路：用分治思想把大问题拆成小问题。

分治三步走
从中间对半分 → 递归排序左右两半 → 合并两个有序子数组
O(n log n)
最坏/平均/最好都一样，比选择排序的 O(n²) 快一个数量级
额外 O(n) 空间
合并步骤需要辅助数组，不是原地（in-place）排序
稳定排序
相等元素的相对顺序在排序后保持不变
适用场景
链表排序、外存/磁盘排序、需要稳定性的场景
合并两摞已排好序的牌对应 →Merge Sort 的合并子过程

每次比较两摞最上面那张牌，把较小的先放进结果，直到一摞空

T(n)=2T(n/2)+O(n)T(n) = 2T(n/2) + O(n)
9第 9 页 · Merge Sort

Merge Sort Demo

上页我们说归并排序的核心是「分而治之」——但只看结论还是模糊。现在用一个具体的小数组，把拆分和合并两步完整走一遍，看清每一步究竟在做什么。

递归拆分到单元素
不断对半分，直到每个子数组只剩一个元素（单元素天然有序，无需再拆）
合并两个有序数组
双指针分别指向两个子数组首部，每次取较小者放入结果数组
需要 O(n) 辅助空间
合并阶段必须借助额外数组暂存结果，完成后再拷回原数组
稳定排序
遇到相等元素时，优先取左侧子数组的，保持原有相对顺序不变
桌上两摞已排好的扑克牌对应 →合并两个有序子数组

每次比较两摞最上面那张牌，把较小的抽走放到结果堆，直到一摞抽完再把另一摞全部倒入

合并代价：两个有序子数组合并需至多 n−1 次比较\text{合并代价：两个有序子数组合并需至多 } n-1 \text{ 次比较}
10第 10 页 · Merge Sort Demo

Hashing

前面我们看到，线性查找要逐个扫、二分查找要折半——都和数组长度有关。有没有办法拿到键就直接知道它在哪儿？

哈希函数
把任意 key 映射成数组下标，计算一步完成
哈希表
按下标把值存到数组对应槽位，期望 O(1) 读写
冲突
不同 key 算出同一槽位，鸽巢原理保证必然出现
解决策略
拉链法（同槽挂链表）/ 开放地址（探下一个空槽）
负载因子
已用槽位比例，越大冲突越多、平均查找越长
快递柜取件对应 →哈希表查找

取件码(key)→柜机算格子号(hash)→直接开门；两件同格挨着放或叠挂

11第 11 页 · Hashing

本节要点

  • ✓不同数据结构对应不同查询代价：数组 O(n)、哈希 O(1)
  • ✓分治将 O(n²) 降到 O(n log n)，关键在合并
  • ✓摊还成本关注操作序列均值，非单次最坏
  • ✓二分查找的隐性前提：输入必须已排序
  • ✓哈希的常数时间代价是冲突处理与函数设计
延伸主题：平衡搜索树（红黑树、B 树）哈希冲突：开放寻址 vs 链地址Quick Sort 与随机化均摊
12第 12 页 · 本节要点

课后思考

先自己思考，再对照参考答案——答案只是路径，不是终点。

1为什么二分查找要求数组有序？如果换成链表存储，还能直接用吗？

参考答案数组支持随机访问 O(1) 取中点；链表只能顺序遍历取中点，整体退化到 O(n)，得不偿失。

2100 万条记录做查找，哈希表和二分查找各自的代价与适用场景是什么？

参考答案哈希表均摊 O(1) 但需哈希函数与额外空间；二分 O(log n) 无需额外空间但依赖有序与随机访问。

3归并排序理论最优，实际运行却常输给快排，瓶颈出在硬件的什么特性上？

参考答案归并频繁申请新数组，缓存命中率低；快排原地操作局部性好，实际常数更小。

13第 13 页 · 课后思考