One Forth

课程主题

算法

计算过程、复杂度与数据结构。

01

课程章节

按难度与先修关系排列

  1. 01难度 3/5序列、栈、队列、树与堆以抽象数据类型和表示不变量比较数组、链表、栈、队列、搜索树与堆，并分析访问、更新和优先操作的成本。先修：编程与科学计算综合项目 · 计数原理、容斥与鸽巢原理约 90 分钟
  2. 02难度 3/5哈希表、图与并查集通过散列函数和冲突处理实现期望常数时间字典，以邻接结构表示图，并用并查集支持近似常数摊还的连通性操作。先修：序列、栈、队列、树与堆 · 图、路径、连通性与树 · 概率模型综合复习约 90 分钟
  3. 03难度 3/5分治、贪心与排序把问题分解为较小实例并合并结果，以递推式分析分治复杂度，并通过交换论证或切分性质证明贪心选择正确。先修：序列、栈、队列、树与堆 · 递推关系与生成函数 · 证明方法约 90 分钟
  4. 04难度 4/5动态规划与图算法用状态和转移复用重叠子问题，结合图遍历、最短路和最小生成树解决结构化优化问题并证明算法不变量。先修：哈希表、图与并查集 · 分治、贪心与排序 · 图、路径、连通性与树约 105 分钟
  5. 05难度 4/5渐近复杂度、归约与可计算性用渐近上界、下界和摊还成本比较算法，通过多项式时间归约表达问题困难性，并由不可判定问题说明计算极限。先修：动态规划与图算法 · 证明方法 · 命题逻辑与量词约 105 分钟
  6. 06难度 4/5数据结构与算法综合复习从问题规模、操作模式和正确性不变量选择数据结构与算法，联合证明、复杂度和边界案例评估分治、贪心、动态规划与图方法。先修：序列、栈、队列、树与堆 · 哈希表、图与并查集 · 分治、贪心与排序 · 动态规划与图算法 · 渐近复杂度、归约与可计算性约 105 分钟