Article

算法导论-CH00-目标

算法导论-CH00-目标，待补充摘要。

June 15, 2026 修考 17 min read

优先级	知识点	必须掌握	大阪大学出现频率
⭐⭐⭐⭐⭐	时间复杂度（Time Complexity）、Big-O	✓	几乎每年
⭐⭐⭐⭐⭐	排序（Sorting）与 Quick Sort、Merge Sort	✓	极高
⭐⭐⭐⭐⭐	Binary Search（二分查找）	✓	极高
⭐⭐⭐⭐⭐	Recursion（递归）与 Divide and Conquer	✓	极高
⭐⭐⭐⭐⭐	Heap（堆）、Priority Queue	✓	高频
⭐⭐⭐⭐⭐	Hash Table（哈希表）	✓	高频
⭐⭐⭐⭐	Linked List（链表）	✓	高频
⭐⭐⭐⭐	Stack、Queue	✓	中高
⭐⭐⭐⭐	Tree（Binary Tree、BST）	✓	中高
⭐⭐⭐⭐	DFS、BFS	✓	中高
⭐⭐⭐⭐	Dynamic Programming（DP）	✓	中高
⭐⭐⭐	Graph 基础	✓	中等
⭐⭐⭐	Dijkstra	建议	偶尔
⭐⭐⭐	Union-Find	建议	偶尔
⭐⭐	Minimum Spanning Tree（Kruskal、Prim）	可选	较少
⭐⭐	Maximum Flow	可选	很少
⭐	NP Complete 等理论	可选	几乎不直接考

算法与数据结构备考规划

第一阶段：算法基础（必须全部掌握）

这一部分几乎每年都会涉及。

首先必须会分析程序运行时间，包括能够计算循环、递归、排序算法的复杂度，并熟悉 $O(1)$ 、 $O(\log n)$ 、 $O(n)$ 、 $O(n \log n)$ 、 $O(n^2)$ 等数量级。京都大学课程资料中也把“算法评价”和复杂度分析放在最前面。

然后要掌握 Recursion（递归） 和 Divide and Conquer（分治），能够手工跟踪递归调用过程、写出递归关系、分析递归深度。

接着必须掌握 Binary Search（二分查找），不仅要会写代码，还要理解循环不变式、前置条件以及正确性证明。九州大学过去问甚至直接要求写出前置条件、循环不变式和后置条件。

最后要掌握 Sorting（排序），包括：

Insertion Sort
Merge Sort
Quick Sort
Heap Sort

尤其是 Quick Sort，经常要求手工执行一次 Partition、分析 Pivot 变化、讨论最坏情况。

第二阶段：数据结构（考试高频）

这一部分建议全部掌握。

需要熟悉 Array、Linked List、Stack、Queue、Hash Table、Heap、Binary Search Tree。

例如：

Hash Table：冲突解决（Linear Probing、Open Addressing）、查找过程、删除问题。
Heap：插入、删除最大值、Heapify、时间复杂度。
Linked List：插入删除操作。
BST：查找、插入、删除。

九州大学和东京大学的算法题中也反复出现 Heap、Hash Table、BST 等内容，可见这是日本院试非常经典的考点。

第三阶段：Graph Algorithms（建议全部掌握）

大阪大学虽然不像东京大学那样大量考图算法，但 DFS/BFS 是非常值得学习的内容。

建议掌握：

Graph 表示方法（Adjacency Matrix、Adjacency List）
DFS（Depth-First Search）
BFS（Breadth-First Search）
Topological Sort
Connected Component
Tree Traversal

如果时间允许，再学习：

Dijkstra
Union-Find
Minimum Spanning Tree（Kruskal）
Maximum Flow（了解思想即可）

京都大学的《アルゴリズムと数据结构》课程也把 Graph、Shortest Path、Maximum Flow 作为后续核心章节。

第四阶段：Dynamic Programming（DP）

DP 在近年的日本院试中越来越重要。

你至少需要掌握：

状态（State）的定义
状态转移（Transition）
Base Case
Memoization（记忆化）
Bottom-up DP

能够解决：

Fibonacci
Knapsack
LIS
区间 DP（了解）

京都大学教材中也专门安排了 DP 与顺序统计量等内容。

日本顶尖院试（东大、阪大、九大）算法复习策略指南

核心研判

你不应该把所有算法都当成“必须背代码”的对象。大阪大学、东京大学、九州大学的题目共同特点是，常常给你一段 C / pseudo code，让你补空、追踪执行结果、写循环不变式、证明复杂度，或者把算法思想改写成程序。

因此真正需要“默写”的不是几十个算法，而是十来个核心模板：

大阪大学（2009–2026）：《アルゴリズムとプログラミング》过去问册覆盖了每年同一科目的题页，说明这门题目长期稳定存在。
东京大学（2002–2026）：目录中反复出现 Dijkstra、dynamic programming、hash table、binary search tree、union-find、maximum flow、minimum spanning tree 等典型主题。
九州大学（H25–R08）：算法题也覆盖 quicksort、linked list、heap、binary search 等基础算法。

第一类：必须达到“可以默写代码”的算法

闭上资料也能写出完整流程。

1. Binary Search（二分查找）

考法特点：九州大学题中直接给出程序并要求写 precondition、loop invariant、postcondition，这种题型非常像日本院试喜欢考的“程序正确性理解”题。九州大学题目明确要求对 binary search 写前置条件、循环不变式和事后条件，这说明它不是只考“会用”，而是考“能解释为什么正确”。
核心要点：必须能默写 while (left <= right) 版本，知道 mid = left + (right-left)/2，知道 A[mid] < key 时移动左端，A[mid] > key 时移动右端，并能说明循环中始终保持“如果 key 存在，则它一定还在当前区间内”。

2. Quick Sort 的 Partition

考法特点：准确地说，你不一定要把整个 Quick Sort 背成某一种固定代码，但 Partition 必须能默写，因为大阪大学和九州大学都喜欢让你追踪数组变化、问 pivot 的位置、问比较次数、问稳定性、问最坏情况。
核心要点：要掌握两种版本：一种是 Lomuto partition，另一种是 Hoare partition。考试中如果给你伪代码，你要能按它推演；如果让你写算法，你用自己熟悉的一种即可。Quick Sort 的主函数只需要记住“partition 后递归处理左右两边”，而 Partition 的细节才是得分核心。

3. Merge Sort（归并排序）

考法特点：它是 Divide and Conquer（分治法）的标准模板，也是分析 $T(n)=2T(n/2)+O(n)=O(n\log n)$ 的最常见材料。这个算法在考试中的作用不只是排序本身，还经常作为“稳定排序”“分治递归式”“为什么是 $O(n\log n)$ ”的标准例子。大阪大学题里曾围绕排序程序、递归调用、比较次数和复杂度进行提问，因此排序算法的代码与复杂度必须熟练。
核心要点：要能写出 merge_sort(l,r)，知道递归到长度 1 停止，然后用 merge 合并两个有序区间。

4. Heap（堆）的两个操作：push 和 pop

考法特点：即 Priority Queue（优先队列）的插入与删除最大值或最小值。九州大学 2014 题直接要求根据优先级构造 heap、连续处理两个最高优先级任务，并证明用 heap 中元素按优先级排序不可能做到 $O(n)$ ，这说明 heap 既考手工构造，也考复杂度下界意识。
核心要点：必须能默写 array-based heap 的下标关系：parent(i)=(i-1)/2，left(i)=2i+1，right(i)=2i+2；插入时放到末尾再 sift-up，删除堆顶时用末尾元素替换根再 sift-down。

5. DFS（Depth-First Search）和 BFS（Breadth-First Search）

考法特点：这两个算法是图算法的底层语言。东京大学目录中出现 directed graph / DFS、directed graph / topological sort、Dijkstra / graph search 等题目，说明图搜索是反复出现的基础主题。
核心要点：DFS 你要能写递归版本，也要知道 visited[v]=true 后遍历邻接点；BFS 你要能写 queue 版本，并知道它在 unweighted graph 中可以求 shortest path。

6. Dijkstra

考法特点：东京大学 2003 直接出现 Dijkstra / graph search，2010 和 2019 又出现 shortest path 相关题目；这说明对东京大学来说，最短路不是边缘知识，而是经典考点。
核心要点：需要默写 priority queue 版本：初始化 dist[s]=0，其他为 INF，每次取出当前距离最小的点，若取出的距离已经不是最新值就跳过，然后对所有 outgoing edges 做 relaxation，即若 dist[to] > dist[v] + cost 则更新。还必须记住前提条件是 edge weight 非负；复杂度在 adjacency list + heap 下是 $O((V+E)\log V)$ ，在朴素实现下是 $O(V^2)$ 。

7. Union-Find / Disjoint Set Union（并查集）

考法特点：东京大学 2010 和 2021 都出现 union-find，这种题很容易要求你写 find、unite、判断是否属于同一集合，或者结合 Kruskal。
核心要点：需要默写带 path compression 和 union by size/rank 的版本。核心代码只有三件事：
- find(x)：若 parent[x]==x 返回 x，否则递归找到根并把 parent[x] 改成根；
- unite(a,b)：先找根，若不同则把小树接到大树；
- same(a,b)：比较两个根是否相同。

8. Dynamic Programming（DP）的基础模板

考法特点：东京大学 2005 出现 sequence matching / dynamic programming，2026 又出现 array segmentation dynamic programming，这说明 DP 在东大中不是偶然题，而是重要方向。真正考试时，DP 的核心不是背题，而是能把题目翻译成 state、transition、initialization、answer。
核心要点：不需要背很多花题，但必须能默写三种基础 DP：
- 一维 DP：例如 Fibonacci 或最大子数组；
- 二维表 DP：例如 edit distance / sequence matching；
- 区间或分割 DP：例如 dp[i]=min(dp[j]+cost(j,i))。

9. Hash Table 的基本操作

考法特点：大阪大学 2009 的题目就是 hash / chain method 风格，东京大学 2006 也出现 hash table / data storage。考试常问：插入后表中状态、查找某个 key 的过程、删除为什么麻烦、平均 $O(1)$ 依赖什么假设。
核心要点：特别注意 chaining 和 open addressing。你要能写出 h(key)，知道 collision（冲突）如何处理；chaining 是每个 bucket 挂 linked list；open addressing 是冲突后继续探测，例如 linear probing。

10. Linked List 的插入和删除

考法特点：九州大学 2013 题中出现用数组模拟两个 linked list，其中一个保存数据，另一个保存 free list，并要求解释函数作用、补全插入代码、追踪执行后的数组状态。这说明 linked list 不只是概念题，而是会考指针更新顺序。
核心要点：必须能写单链表插入：new->next = prev->next; prev->next = new，也要能写删除：prev->next = prev->next->next。如果是双向链表，还要能同时更新 prev 与 next。

第二类：最好能默写伪代码，但不一定背完整 C 代码的算法

Topological Sort（拓扑排序）
- 考法与建议：东京大学 2018 出现 directed graph / topological sort，所以你要知道两种写法：DFS 结束时间逆序，或者 Kahn algorithm（入度为 0 的点入队，反复删除）。考试中更推荐背 Kahn，因为它更容易手算，也更容易解释“如果最后输出点数小于 $V$ ，说明有 cycle”。
Minimum Spanning Tree（最小生成树）
- 考法与建议：东京大学 2025 出现 minimum spanning tree，Kruskal 的代码和 Union-Find 天然绑定：把边按权重排序，依次考虑最小边，如果两个端点不在同一连通分量，就加入 MST 并 unite。你不一定需要默写 Prim 的优先队列版本，但 Kruskal 必须会，因为它短、稳定、容易写证明。
Maximum Flow（最大流）
- 考法与建议：对大阪大学不是第一优先级，但对东京大学需要至少能默写 Ford-Fulkerson / Edmonds-Karp 的思想。东京大学 2023 出现 maximum flow / bipartite matching，这类题常把二部匹配转成流网络。你至少要能写：在 residual graph 中找一条 augmenting path，沿路径增加可行流量，更新正向边和反向边，直到找不到增广路。完整实现较长，不建议作为大阪主线最优先背，但如果你同时准备东大，就不能只停留在“听过”。
Euclidean Algorithm（欧几里得算法）
- 考法与建议：尤其是 Extended Euclidean Algorithm。东京大学 2002 题直接考 Euclidean algorithm，并且题面要求证明循环中的关系保持，属于典型的“算法 + 不变式 + 正确性证明”题。你应该能默写 while b != 0: (a,b)=(b,a%b)，也要知道扩展欧几里得维护 $ax+by=\gcd(a,b)$ 的系数更新。

三校真题综合：默写优先级总览

优先级	覆盖算法
第一优先级 (必须写到几乎不出错)	Binary Search、Quick Sort Partition、Merge Sort、Heap push/pop、DFS、BFS、Dijkstra、Union-Find、基础 DP、Hash Table、Linked List
第二优先级 (要能写出伪代码并能手工推演)	Topological Sort、Kruskal、Euclidean / Extended Euclidean、BST search/insert/delete、Maximum Subarray
第三优先级 (知道思想并能在题目引导下写出)	Maximum Flow、Bipartite Matching、Floyd-Warshall、Bellman-Ford、Knapsack、Edit Distance、Pattern Matching

总结：高效背诵标准

对你来说，最合理的背诵标准不是“背一堆代码”，而是每个算法都背成四句话：

它解决什么问题；
核心数据结构是什么；
伪代码主循环怎么写；
复杂度是多少。

示例（Dijkstra）：

“非负权单源最短路，用 priority queue，每次取当前最小 dist 的点并 relax 邻边，复杂度 $O((V+E)\log V)$ ”。

能做到这一步，再配合 5 到 10 次手写，你就已经达到大阪大学、东京大学、九州大学算法题所需要的“默写能力”了。