COMP90038 · Algorithms and ComplexityCOMP90038 · 算法与复杂度
UniMelb's graduate gateway to algorithm design — asymptotic analysis, classic data structures, and the four core design paradigms.墨大研究生算法设计入门课 —— 渐进复杂度分析、经典数据结构，以及四大核心算法设计范式。COMP90038 teaches you to design efficient algorithms and reason formally about their complexity, covering asymptotic notation, abstract data types (queues, trees, priority queues, graphs), and the brute-force, divide-and-conquer, dynamic-programming and greedy paradigms. Assessment is two assignments, weekly quizzes, and a 60% final exam. This guide is built from 37 real COMP90038 course materials in the AskSia Library.
COMP90038 教你设计高效算法并对其复杂度进行严格分析，内容涵盖渐进记号、抽象数据类型（队列、树、优先队列、图），以及暴力法、分治、动态规划与贪心四大范式。考核为两次作业、每周小测，外加占 60% 的期末闭卷考试。本指南基于AskSia Library 中 37 份真实 COMP90038 课程材料整理而成。
Built from 37 real COMP90038 course materials in the AskSia Library.
基于AskSia Library 中 37 份真实 COMP90038 课程材料整理而成。
What COMP90038 is aboutCOMP90038 讲什么
COMP90038 Algorithms and Complexity is a graduate-level subject in the School of Computing and Information Systems at the University of Melbourne. It introduces the theory of computational efficiency and the classic algorithms and data structures used to solve fundamental problems — computing distances in networks, searching large collections, and sorting. Students learn to analyse algorithm complexity using asymptotic notation, work with abstract data types such as queues, trees, priority queues and graphs, and apply the four core design paradigms: brute force, divide-and-conquer, dynamic programming and greedy. The subject also covers space–time trade-offs and the theoretical limits of algorithmic power.
COMP90038《算法与复杂度》是墨尔本大学计算与信息系统学院开设的研究生科目。它讲授计算效率理论，以及用来解决基础问题（如网络中的最短距离、大规模集合的查找与排序）的经典算法和数据结构。学生将学会用渐进记号分析算法复杂度，掌握队列、树、优先队列、图等抽象数据类型，并运用暴力法、分治、动态规划、贪心四大核心设计范式；课程还涉及空间—时间权衡以及算法能力的理论极限。
The COMP90038 syllabus, topic by topicCOMP90038 大纲 · 逐个主题
Asymptotic notation & complexity classes渐进记号与复杂度分类
Big-O, Big-Omega and Big-Theta notation to describe how an algorithm's running time and space grow with input size. The foundation for comparing algorithms independently of hardware.
用大 O、大 Ω、大 Θ 记号刻画算法运行时间与空间随输入规模的增长趋势，是脱离硬件横向比较算法效率的基础。
Analysis of algorithms (mathematical & empirical)算法分析（数学分析与经验分析）
Deriving the cost of non-recursive and recursive algorithms, setting up and solving recurrence relations, and measuring performance empirically by timing real runs.
推导非递归与递归算法的代价，建立并求解递推关系式，并通过实际运行计时进行经验性能测量。
Fundamental data structures基础数据结构
Arrays, linked lists, stacks and queues — their representations and the cost of core operations, plus how the choice of structure drives an algorithm's efficiency.
数组、链表、栈与队列的表示方式及核心操作代价，以及数据结构选择如何决定算法效率。
Trees, priority queues & heaps树、优先队列与堆
Binary search trees (inorder traversal yields keys in sorted order, but height can degrade to O(n)), and the two self-balancing structures COMP90038 examines: AVL trees — kept balanced via R / L / LR / RL rotations at the lowest node whose balance factor (height of left minus height of right) reaches ±2 — and 2-3 trees, where an overflowing 3-node splits and promotes its middle key. Heaps are complete binary trees stored in an array (children of node i at 2i and 2i+1); heapify runs in O(n), and heapsort, push, pop and update-key each cost O(log n).
二叉搜索树（中序遍历给出有序的键，但高度可能退化为 O(n)），以及 COMP90038 考查的两种自平衡结构：AVL 树——在平衡因子（左子树高减右子树高）达到 ±2 的最低节点处通过 R / L / LR / RL 旋转维持平衡——与 2-3 树，其中溢出的 3-节点会分裂并把中间键上提。堆是用数组存储的完全二叉树（节点 i 的子节点位于 2i 与 2i+1）；建堆为 O(n)，堆排序、入堆、出堆与改键各为 O(log n)。
Hashing & space–time trade-offs哈希与空间—时间权衡
Hash tables, collision handling, and the general principle of trading extra memory for faster access (e.g. input enhancement and precomputation).
哈希表、冲突处理，以及用额外内存换取更快访问的一般原理（如输入增强与预计算）。
Brute force & exhaustive search暴力法与穷举搜索
The brute-force design paradigm: straightforward but often costly approaches such as sequential search, selection/bubble sort, and exhaustive enumeration.
暴力设计范式：直接但常常代价高昂的方法，如顺序查找、选择/冒泡排序与穷举枚举。
Divide-and-conquer分治法
Splitting a problem into subproblems, solving recursively, and combining results — mergesort (Θ(n log n), stable, the optimal comparison sort) and quicksort (O(n log n) expected, O(n²) worst case). The course requires you to apply the Master Theorem to any recurrence T(n)=a·T(n/b)+Θ(n^d): compare a against b^d — a < b^d gives Θ(n^d), a = b^d gives Θ(n^d log n), a > b^d gives Θ(n^{log_b a}). Reconstructing a tree's postorder from its preorder and inorder traversals is a recurring exam mechanic here.
将问题拆分为子问题、递归求解再合并结果——归并排序（Θ(n log n)，稳定，最优的比较排序）与快速排序（期望 O(n log n)，最坏 O(n²)）。本课要求你对任意递推式 T(n)=a·T(n/b)+Θ(n^d) 套用主定理：比较 a 与 b^d——a < b^d 得 Θ(n^d)，a = b^d 得 Θ(n^d log n)，a > b^d 得 Θ(n^{log_b a})。由前序与中序遍历重建出树的后序遍历是这里反复出现的考点。
Graphs & graph algorithms图与图算法
Adjacency matrix (O(V²) space, O(1) edge test) versus adjacency lists (O(V+E)) — this representation choice sets traversal cost at O(V²) versus O(V+E). One unified framework drives both traversals: a stack gives DFS, a queue gives BFS (and in an unweighted graph the BFS tree is the shortest-path tree). DFS-based topological sort emits nodes in reverse finish order, with ties broken alphabetically in the exam; connected components are found by repeated flood-fill in O(V+E). Warshall computes transitive closure (R^k via ∨/∧) and Floyd computes all-pairs shortest paths (D^k via min/+), both Θ(n³).
邻接矩阵（O(V²) 空间，O(1) 边判定）对比邻接表（O(V+E)）——这一表示选择决定了遍历代价是 O(V²) 还是 O(V+E)。一套统一框架驱动两种遍历：用栈得 DFS，用队列得 BFS（在无权图中，BFS 树即最短路径树）。基于 DFS 的拓扑排序按逆完成顺序输出节点，考试中并列时按字母序打破；连通分量通过重复 flood-fill 以 O(V+E) 求得。Warshall 计算传递闭包（R^k 用 ∨/∧），Floyd 计算全源最短路（D^k 用 min/+），二者均为 Θ(n³)。
Dynamic programming动态规划
Solving problems with overlapping subproblems by storing intermediate results, avoiding redundant recomputation.
针对含重叠子问题的问题，通过存储中间结果避免重复计算来求解。
Greedy algorithms贪心算法
Making the locally optimal choice at each step, and the conditions under which this yields a globally optimal solution (e.g. minimum spanning trees, Dijkstra).
每步做出局部最优选择，以及这种策略能得到全局最优解的条件（如最小生成树、Dijkstra 算法）。
Limits of algorithmic power算法能力的极限
Lower bounds, decision trees, and an introduction to the theoretical limits of what algorithms can achieve, including the P vs NP distinction.
下界、决策树，以及对算法能力理论极限的引入，包括 P 与 NP 之分。
How COMP90038 is assessedCOMP90038 怎么考核
Final exam: Yes期末考试：有| Component考核项 | Weight占比 | Note说明 |
|---|---|---|
| Weekly online quizzes (10 quizzes, 1% each)每周在线小测（共 10 次，每次 1%） | 10% | One short quiz most teaching weeks across the semester.学期内大部分教学周各有一次简短小测。 |
| Assignment 1作业一 | 15% | Due around Week 6.约第 6 周提交。 |
| Assignment 2作业二 | 15% | Due around Week 11.约第 11 周提交。 |
| Final examination (3-hour)期末考试（3 小时） | 60% | Held in the end-of-semester exam period. Hurdle: must score at least 30/60 on the exam, and at least 50/100 overall, to pass.在学期末考试周举行。门槛要求：期末考至少 30/60，且总评至少 50/100 方可通过。 |
40% coursework (two 15% assignments + 10% weekly quizzes) + a 60% final exam, which is a hurdle (≥30/60 on the exam and ≥50/100 overall required to pass).
40% 平时分（两次各 15% 的作业 + 10% 每周小测）＋ 60% 期末考；期末考为门槛项（须达 30/60，且总评须达 50/100 才能通过）。
When each COMP90038 task is dueCOMP90038 各项考核时间
Test yourself: COMP90038 practice questions自测一下：COMP90038 练习题
- Θ(n)
- Θ(n log n)
- Θ(n^1.5)
- Θ(√n)
- Θ(n)
- Θ(n log n)
- Θ(n^1.5)
- Θ(√n)
Show answer查看答案
- 18 and 25
- 18 and 40
- 18 and 30
- 18 and 27
- 18 与 25
- 18 与 40
- 18 与 30
- 18 与 27
Show answer查看答案
- [7, 9, 8, 14, 11]
- [8, 9, 7, 14, 11]
- [7, 9, 8, 11, 14]
- [8, 11, 7, 14, 9]
- [7, 9, 8, 14, 11]
- [8, 9, 7, 14, 11]
- [7, 9, 8, 11, 14]
- [8, 11, 7, 14, 9]
Show answer查看答案
High-value exam questions in COMP90038COMP90038 高频考点 · 考试风格题
A worked COMP90038 problemCOMP90038 例题
Nearest of k sites, in O((n+m) log n) — independent of k在 O((n+m) log n) 内求每个点到 k 个站点中最近者——与 k 无关
You are given a weighted, non-negative graph G with n nodes and m edges, and a set of k special 'site' nodes (e.g. hospitals). For every node in the graph, report the distance to its nearest site. The naive approach — run Dijkstra once from each of the k sites — costs O(k·(n+m) log n), which is too slow when k is large. Design an algorithm that runs in O((n+m) log n), independent of k.
给定一个非负权图 G，含 n 个节点、m 条边，以及一组 k 个特殊「站点」节点（如医院）。请为图中每个节点报告其到最近站点的距离。朴素做法——从 k 个站点各跑一次 Dijkstra——代价为 O(k·(n+m) log n)，当 k 较大时太慢。请设计一个运行在 O((n+m) log n)、与 k 无关的算法。
Add a virtual super-source s* and connect it to every site with a 0-weight edge. Run a single Dijkstra from s* on this augmented graph: because every site sits at distance 0 from s*, the shortest path from s* to any node v passes through v's nearest site, so dist(s*, v) is exactly the distance to the nearest site. To name which site is nearest, run one DFS over the resulting shortest-path tree tracking the most-recent site seen on the path from the root — the lowest site-ancestor of each node is its nearest site. Augmenting is O(k), the single Dijkstra is O((n+1+m+k) log n) = O((n+m) log n) since k ≤ n, and the DFS is O(n+m). Trap: do not run a per-site Dijkstra; the whole point is the super-source insight, and you must justify k ≤ n to collapse the bound.
新增一个虚拟超级源点 s*，用 0 权边把它连到每个站点。在这个扩展图上从 s* 跑一次 Dijkstra：由于每个站点到 s* 的距离都是 0，从 s* 到任意节点 v 的最短路必经过 v 的最近站点，因此 dist(s*, v) 恰为到最近站点的距离。要指出具体是哪个站点最近，再对所得最短路径树跑一次 DFS，沿根到当前节点的路径记录最近遇到的站点——每个节点的最低站点祖先即其最近站点。扩展为 O(k)，单次 Dijkstra 为 O((n+1+m+k) log n) = O((n+m) log n)（因 k ≤ n），DFS 为 O(n+m)。陷阱：不要按站点逐个跑 Dijkstra；关键在于超级源点这一洞见，且需论证 k ≤ n 才能把界收紧。
COMP90038 glossaryCOMP90038 术语表
- Asymptotic notation (Big-O / Θ / Ω)渐进记号（大 O / Θ / Ω）
- Notation describing the growth rate of an algorithm's cost as input size approaches infinity.
- 描述输入规模趋于无穷时算法代价增长速率的记号。
- Recurrence relation递推关系式
- An equation expressing an algorithm's cost in terms of its cost on smaller inputs, used to analyse recursive algorithms.
- 用更小输入上的代价来表达算法代价的方程，用于分析递归算法。
- Abstract data type (ADT)抽象数据类型（ADT）
- A data type defined by its operations and behaviour rather than its implementation (e.g. queue, priority queue, graph).
- 由其操作与行为而非具体实现来定义的数据类型（如队列、优先队列、图）。
- Divide-and-conquer分治
- A paradigm that splits a problem into subproblems, solves them recursively, and combines the results.
- 将问题分解为子问题、递归求解再合并结果的设计范式。
- Dynamic programming动态规划
- Solving problems with overlapping subproblems by storing and reusing intermediate results.
- 对含重叠子问题的问题，通过存储并复用中间结果来求解的方法。
- Greedy algorithm贪心算法
- A strategy that makes the locally optimal choice at each step in the hope of reaching a global optimum.
- 每步选择局部最优、期望达到全局最优的策略。
- Priority queue / heap优先队列 / 堆
- An ADT serving the highest-priority element first, commonly implemented as a binary heap.
- 优先弹出最高优先级元素的抽象数据类型，常用二叉堆实现。
- Hash table哈希表
- A structure mapping keys to slots via a hash function for near-constant-time lookup, trading space for speed.
- 通过哈希函数将键映射到槽位、以近常数时间查找的结构，以空间换速度。
- Spanning tree (MST)生成树（最小生成树 MST）
- A subgraph connecting all vertices of a graph with no cycles; the minimum-weight version is the MST.
- 连接图中所有顶点且无环的子图；权值最小者为最小生成树。
- P vs NPP 与 NP
- The distinction between problems solvable in polynomial time (P) and those whose solutions are merely verifiable in polynomial time (NP).
- 可在多项式时间内求解的问题（P）与解仅可在多项式时间内验证的问题（NP）之间的区分。
- Master Theorem主定理
- A closed-form rule for T(n)=a·T(n/b)+Θ(n^d): compare a with b^d to read off Θ(n^d), Θ(n^d log n) or Θ(n^{log_b a}). COMP90038 expects you to identify the parameters and name the case.
- 针对 T(n)=a·T(n/b)+Θ(n^d) 的闭式规则：比较 a 与 b^d，直接得出 Θ(n^d)、Θ(n^d log n) 或 Θ(n^{log_b a})。COMP90038 要求你识别参数并指明所属情形。
- Balance factor平衡因子
- For an AVL-tree node, the height of its left subtree minus that of its right subtree; the AVL invariant keeps it in {−1, 0, +1}, triggering a rotation when it reaches ±2.
- AVL 树中某节点左子树高度减右子树高度之差；AVL 不变式将其保持在 {−1, 0, +1}，当达到 ±2 时触发旋转。
- Horspool's algorithmHorspool 算法
- An input-enhancement string-matching method that precomputes a shift table from the pattern and matches right-to-left; the shift is governed by the text character aligned with the pattern's last position. It is the only string-search algorithm examined (Boyer-Moore, KMP and Rabin-Karp are not).
- 一种输入增强的字符串匹配方法，先由模式预计算移位表，再从右向左匹配；移位量由与模式末位对齐的文本字符决定。它是唯一被考查的字符串搜索算法（Boyer-Moore、KMP、Rabin-Karp 不在考查范围）。
- Universal hashing全域哈希
- Choosing a hash function at random from a 2-universal family so that no fixed input can be made to collide adversarially, giving O(1) expected query time with O(n) space.
- 从 2-全域哈希族中随机选取哈希函数，使得没有固定输入能被对手构造成必然碰撞，从而以 O(n) 空间获得 O(1) 期望查询时间。
COMP90038 — common questionsCOMP90038 常见问题
How is COMP90038 assessed?COMP90038 怎么考核？
Is there a final exam in COMP90038?COMP90038 有期末考吗？
Do I need programming or maths background for COMP90038?学 COMP90038 需要编程或数学基础吗？
What's the difference between COMP90038 and an undergraduate algorithms subject?COMP90038 和本科算法课有什么区别？
Is AskSia allowed under the University of Melbourne academic integrity policy?墨尔本大学的学术诚信政策允许用 AskSia 吗？
Other UniMelb course guides墨大 其他课程指南
AskSia is an independent study aid and is not affiliated with, endorsed by, or sponsored by The University of Melbourne. Course details may change — always confirm against the official handbook. Read about how this guide is built. AskSia 是独立的学习辅助工具，与墨尔本大学没有任何隶属、背书或赞助关系。课程信息可能变动，请始终以官方 handbook 为准。了解本指南的编写方法。