为什么‘旅行商’和‘背包’这类问题让我们头疼？
Why do problems like TSP and knapsack give us headaches?
它们属于 NP 难：目前没有已知能在多项式时间内精确求解的算法，输入稍大就爆炸式变难。实际靠近似、动态规划或启发式在可接受误差内解决。
They are NP-hard: no known polynomial-time exact algorithm, and difficulty explodes with size. In practice we use approximation, dynamic programming or heuristics within acceptable error.
难度 专业 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-10-04
来源 · Source
Applegate、Bixby、Chvatal 与 Cook,《The Traveling Salesman Problem》,Princeton University Press,2006
D. L. Applegate et al., The Traveling Salesman Problem, Princeton University Press, 2006
独立核验依据 · Independent verification: 核验依据 1 ISBN 9780691129938 (2006)
#复杂度 #NP难
P与NP问题到底在问什么？假如某个NP完全问题——例如旅行商问题的判定版本——被找到多项式时间算法，密码学与复杂性理论将发生怎样的连锁崩塌？
What is the P versus NP question really asking — and if some NP-complete problem, say the decision version of the traveling salesman problem, were found a polynomial-time algorithm, what chain reaction would sweep through cryptography and complexity theory?
它在问：凡是答案容易验证的问题，是否都同样容易解答？P类问题可在多项式时间内求出答案，NP类问题的候选答案可在多项式时间内核对；二者是否相等悬置逾五十年，位列克雷数学研究所千禧年七大难题之首。一旦某个NP完全问题获得多项式算法，依据库克-列文定理的多项式归约，所有NP问题随之可解，RSA等公钥体系的难度根基将即刻瓦解。
It asks whether every problem whose answers are easy to verify is also easy to solve. Problems in P admit polynomial-time solutions; candidate answers to problems in NP can be checked in polynomial time; whether the two classes coincide has hung open for over half a century, heading the Clay Mathematics Institute's seven Millennium Problems. The moment any NP-complete problem gains a polynomial algorithm, polynomial reductions via the Cook-Levin theorem make all NP problems tractable too, instantly dissolving the hardness foundation of public-key schemes such as RSA.
难度 专业 · 适合 小学高段(9-12)
CC BY 4.0 · 已核验 · Verified 2026-11-04
来源 · Source
S. A. Cook,《The complexity of theorem-proving procedures》,Proceedings of the third annual ACM symposium on Theory of computing (STOC),1971 (DOI: 10.1145/800157.805047)
S. A. Cook, 'The complexity of theorem-proving procedures', Proceedings of the third annual ACM symposium on Theory of computing (STOC), 1971, DOI: 10.1145/800157.805047
独立核验依据 · Independent verification: 核验依据 1 Crossref DOI 10.1145/800157.805047
#P/NP问题 #NP完全 #库克-列文定理
快速排序平均为什么是 O(n log n)？
Why is quicksort average O(n log n)?
每次划分把数组大致对半分，需约 log n 层，每层总计扫描 O(n) 个元素，故平均 O(n log n)。最坏（已排序且总选端点）会退化到 O(n²)。
Each partition splits the array roughly in half, needing about log n levels, and each level scans O(n) elements total, giving average O(n log n). The worst case (sorted input, bad pivot) degrades to O(n²).
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
Martzloff, J.-C., 《中国数学史》, Springer
Martzloff, J.-C., 'A History of Chinese Mathematics', Springer
独立核验依据 · Independent verification: 核验依据 1 OPENLIBRARY 标识 /works/OL32240873W：A History of Chinese M
#复杂度 #排序
傅里叶变换把信号拆成了什么？
What does the Fourier transform decompose a signal into?
它把随时间变化的信号分解成不同频率的正弦波叠加，让你看到‘含有哪些频率、各占多少’。音乐均衡器和图像压缩都建立在它之上。
It breaks a time signal into a sum of sine waves of different frequencies, revealing which frequencies are present and how strongly. Audio equalizers and image compression build on it.
难度 进阶 · 适合 小学低段(6-8)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
同济大学数学系 编,《高等数学》第7版,高等教育出版社,2014
Tongji University Dept. of Math, Advanced Mathematics, 7th ed., Higher Education Press, 2014
独立核验依据 · Independent verification: 核验依据 2 ISBN 9787040396638（豆瓣书目条目: 高等数学·上册）
#傅里叶 #频率
动态规划和‘暴力枚举’差在哪？
How does dynamic programming differ from 'brute-force enumeration'?
暴力把子问题重复算很多遍；动态规划把已算的结果存起来复用（记忆化），把指数级开销压成多项式。典型如最长公共子序列、背包问题。
Brute force recomputes subproblems repeatedly; dynamic programming stores and reuses results (memoization), turning exponential cost into polynomial. Classic for longest common subsequence and knapsack.
难度 进阶 · 适合 小学高段(9-12)
CC BY 4.0 · 已核验 · Verified 2026-10-03 · 2 条独立证据
来源 · Source
Bellman《动态规划》(1957)；Cormen 等《算法导论》
Bellman, 'Dynamic Programming' (1957); Cormen et al., 'Introduction to Algorithms'
独立核验依据 · Independent verification: 核验依据 1 ISBN 978-0-262-04630-5 · 核验依据 2 ISBN 9780691079516 (1957)
#复杂度 #动态规划
为什么‘排序’是计算机里的基本功？
Why is 'sorting' a basic skill in computing?
许多任务（查找、去重、合并、中位数）都先排序会更快；而比较排序的理论下界是 O(n log n)，是算法课的第一个重要结论。
Many tasks (search, dedupe, merge, median) get faster after sorting; the theoretical lower bound for comparison sorting is O(n log n), a first key result in algorithms.
难度 入门 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-10-03 · 2 条独立证据
来源 · Source
《算法导论》Cormen 等
Introduction to Algorithms by Cormen Leiserson Rivest and Stein
独立核验依据 · Independent verification: 核验依据 1 ISBN 978-0-262-04630-5 · 核验依据 2 ISBN 9780691079516 (1957)
#复杂度 #排序