CS170：高效算法与难解问题

以本地 Fall 2023 资料为权威来源，系统学习分治、图算法、贪心、动态规划、线性规划、网络流与 NP 完全性；收录 13 份 Discussion、14 份 Homework 及本地官方解答。

面对越来越大的输入，怎样同时证明算法会停、答案正确，并让代价增长得足够慢？

加州大学伯克利分校

John Wright、Nika Haghtalab

2023 年秋季

从这里开始

序言：算法、斐波那契与渐近分析

已完成 0 / 10 讲 · 记录保存在当前浏览器

0 / 10讲义已完成

已完成 0 / 27 份实践
由你确认，不自动标记

读讲义，理解原理与机制。
明确输入、候选解、递推或图上的局部选择。

做讨论题，自己推一遍。
在每次迭代、分治或交换论证后检查正确性为何仍成立。

用工作簿与实验验证方法。
改变权重或输入规模，测试贪心、复杂度与最优性边界。

怎样把问题拆成可计算的部分？

局部选择何时保证全局正确？

怎样表示并优化可行解？

哪些问题无法期待高效精确解？

先预测，再动手推，最后对照解析。

把理解落到可检查的推导、测试与实现证据。