第1章：计算复杂性基础
大家好，我是这门课的主讲人。今天咱们聊聊计算复杂性——说白了，就是研究「一个问题到底有多难」。
你可能觉得这很抽象。但我告诉你，这玩意儿在实际项目中特别重要。我曾经接手过一个物流调度系统，一开始用的算法跑小数据还行，数据量一上来，服务器直接卡死。后来才发现，我碰上的其实是个NP难问题。
嗯，从那天起，我就老老实实补了计算复杂性的课。
1.1 什么是P类问题？
P类问题，全称Polynomial time。意思是：存在一个算法，能在多项式时间内解决它。
什么叫多项式时间？就是时间复杂度是 O(n²)、O(n³) 这种。n 是输入规模。你想想看，n 从100涨到1000，运行时间最多也就涨个几千倍。这在工程上是可以接受的。
举个例子：排序。你给100个数排序，和给1000个数排序，时间差不了太多。这就是P类问题。
核心判断标准：如果一个问题能在 O(n^k) 时间内解决（k是常数），它就是P类问题。
我个人习惯把P类问题叫做「好解决的问题」。虽然有时候常数很大，但至少心里有底。
1.2 NP类问题是什么？
NP类问题，全称Nondeterministic Polynomial time。注意，NP不是「非P」，而是「非确定性多项式」。
怎么理解？我给你一个解，你能在多项式时间内验证它对不对。但你自己去找这个解，可能很难。
举个例子：数独。我给你一个填好的数独，你检查一下每行每列每宫有没有重复，几分钟就搞定。但让你自己从头解一个数独，可能得花半小时。
这就是NP问题的本质：验证容易，求解难。
我的经验：在项目中，如果你遇到一个问题，能快速验证某个方案是否可行，但自己找方案很费劲，那它大概率是NP问题。
1.3 NP完全问题——最难的那一批
NP完全问题，简称NPC。它是NP问题里最难的那一批。
难到什么程度？只要你能解决任何一个NPC问题，所有NP问题就都能解决。反过来，如果你能证明某个NPC问题不存在多项式算法，那所有NP问题都不存在多项式算法。
这就像多米诺骨牌。推倒第一张，后面全倒。
常见的NPC问题有：
- 旅行商问题（TSP）：找一条最短路径，经过所有城市恰好一次
- 背包问题（KP）：在容量限制下，选哪些物品能让总价值最大
- 图着色问题：用最少的颜色给图的顶点染色，相邻顶点颜色不同
这三个问题，我后面会专门用几章来讲。这里先混个脸熟。
1.4 NP难问题——比NPC还难
NP难问题，简称NP-hard。它比NPC还「狠」。
NPC问题至少还是NP问题——给你一个解，你还能验证。但NP难问题可能连验证都做不到。
举个例子：停机问题。给你一段程序，问它会不会永远运行下去。这个问题连验证都做不到——你没法判断它到底是在「运行中」还是「死循环」。
NP难问题在工程中很常见。比如：
- 大规模集成电路布局优化
- 蛋白质结构预测
- 某些金融风险模型
避坑指南：我曾经在做一个排班系统时，想用精确算法求解。跑了三天三夜没出结果。后来才发现，这其实是个NP难问题。嗯，从那以后，我遇到大规模问题，第一反应就是：先判断它是不是NP难。
1.5 常见NP难组合优化问题详解
1.5.1 旅行商问题（TSP）
问题描述：有n个城市，两两之间有距离。找一条路径，从某个城市出发，每个城市恰好访问一次，最后回到起点，要求总距离最短。
数学形式：
min Σ d(i,j) * x(i,j)
约束：
- 每个城市恰好进入一次：Σ x(i,j) = 1
- 每个城市恰好离开一次：Σ x(i,j) = 1
- 不能有子回路（subtour elimination）
- x(i,j) ∈ {0,1}n=10个城市时，暴力枚举要算 10! ≈ 362万种路径。n=20时，20! ≈ 2.4×10¹⁸，现代计算机也扛不住。
这就是为什么TSP是NP完全问题的「明星代表」。
1.5.2 背包问题（KP）
问题描述：有一个容量为C的背包，n个物品，每个物品有重量w(i)和价值v(i)。选哪些物品装进去，能让总价值最大，且总重量不超过C。
数学形式：
max Σ v(i) * x(i)
约束：
- Σ w(i) * x(i) ≤ C
- x(i) ∈ {0,1}背包问题有个特点：当物品重量和价值都是整数时，可以用动态规划在 O(nC) 时间内求解。但C很大时，这个算法就失效了。
我的建议：实际项目中，如果C不大（比如几千），动态规划是首选。如果C很大，考虑用贪心或遗传算法。
1.5.3 图着色问题
问题描述：给定一个无向图，用最少的颜色给每个顶点染色，要求相邻顶点颜色不同。
这个问题的难点在于：你没法提前知道最少需要几种颜色。对于一般图，最少颜色数等于图的色数（chromatic number），而求色数本身就是NP难的。
实际应用：
- 考试安排：同一时间不能考两门有冲突的科目
- 寄存器分配：编译器里给变量分配寄存器
- 频率分配：无线通信中避免信号干扰
1.6 知识体系总览
下面这张图，是我自己画的。它把本章的核心概念串起来了。你多看几遍，后面学起来会轻松很多。
1.7 本章小结
这一章我们聊了：
- P类问题：多项式时间可解，工程上放心用
- NP类问题：验证容易，求解难
- NP完全问题：NP中最难的一批，TSP、KP、图着色是代表
- NP难问题：比NPC还难，连验证都做不到
记住一句话：遇到问题先分类，分类之后再选算法。这是我在项目里摔过跟头后总结出来的。
下一章，我们会深入TSP，看看它到底难在哪里，以及有哪些实用的求解方法。
公众号:蓝海资料掘金营，微信deep3321