为什么“P 对 NP”问题被列为千禧年难题？
Why is 'P vs NP' one of the Millennium Prize problems?
P 是能快速验证并快速求解的问题类，NP 是能快速验证答案的问题类。若 P=NP，则大量看似难解的问题（如旅行商、整数分解的某些变体）都能快速求解，会颠覆密码学与优化；若不等则解释为何这些难题至今无解。它既影响理论也影响现实安全。
P is problems solvable fast, NP problems whose answers are fast to verify. If P=NP, many hard problems (TSP, scheduling) become fast to solve, upending cryptography and optimization; if not, it explains why they resist solution. It bridges theory and real security.
难度 专业 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Michael Sipser,《Introduction to the Theory of Computation》第3版,Cengage Learning,2012
M. Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage Learning, 2012
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL19859284W：Introduction to the th
#P-NP #复杂性
摊还分析（amortized analysis）和 worst-case 分析有什么区别？
How does amortized analysis differ from worst-case analysis?
最坏情况分析看单次操作的最大开销，而摊还分析看一系列操作的总开销除以次数，允许偶尔很贵、平时很便宜。例如动态数组偶尔扩容很慢，但平均每次插入仍是常数时间。
Worst-case looks at the cost of a single operation; amortized analysis averages the total cost of a sequence, allowing rare expensive steps. A dynamic array occasionally resizes slowly, yet average insertion stays O(1).
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Cormen, Leiserson, Rivest, Stein,《Introduction to Algorithms》第3版,MIT Press,2009
T. H. Cormen et al., Introduction to Algorithms, 3rd ed., MIT Press, 2009
独立核验依据 · Independent verification: 核验依据 2 ISBN 978-0-262-04630-5
#摊还 #复杂度
主定理（Master Theorem）是用来算什么的？
What is the Master Theorem used to compute?
主定理给出分治递归 T(n)=a·T(n/b)+f(n) 的渐近解，通过比较递归规模与合并代价 f(n) 的大小，直接判断时间复杂度属于 O(n^log_b a)、O(f(n)) 还是二者相乘的对数级别，省去展开递归树。
The Master Theorem solves divide-and-conquer recurrences T(n)=aT(n/b)+f(n) by comparing the recursive part n^log_b a with the combine cost f(n), directly yielding the asymptotic bound without expanding the recursion tree.
难度 进阶 · 适合 小学高段(9-12)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Cormen, Leiserson, Rivest, Stein,《Introduction to Algorithms》第3版,MIT Press,2009
T. H. Cormen et al., Introduction to Algorithms, 3rd ed., MIT Press, 2009
独立核验依据 · Independent verification: 核验依据 2 ISBN 978-0-262-04630-5
#主定理 #递归