算法的复杂性与分析
算法分析量化了算法运行时间和内存随输入规模增长的情况，提供了渐近词汇和工具，用于比较算法和识别本质上困难的问题。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
算法分析是研究算法作为其输入规模的函数所消耗的计算资源（主要是时间和空间），以及用于推导、表达和比较这些资源界限的技术。
Scope
该领域涵盖算法资源使用的测量和比较：渐近符号（大O、大Omega、大Theta）、递归算法产生的递推关系求解、操作序列的摊还分析，以及计算复杂性类和NP完全性的基本原理及其在算法设计中的应用。它涉及最坏情况、平均情况和摊还成本，以及可处理问题和难处理问题之间的区别。更广泛的计算理论（可计算性、形式复杂性类）属于一个独立的子领域；此处重点是分析具体算法。
Sub-topics
Core questions
- 如何独立于机器和实现细节来表达算法的资源使用？
- 最坏情况、平均情况和摊还分析分别告诉我们什么？
- 如何求解递归算法产生的递推关系以获得渐近界限？
- 我们如何建立下界以表明没有算法能做得更好？
- 一个问题是NP完全的意味着什么，以及它对设计为何重要？
Key concepts
- 大O、大Omega、大Theta
- 最坏情况和平均情况分析
- 递推关系
- 主定理
- 摊还分析
- 下界
- 多项式时间
- NP完全性
Key theories
- 渐近符号
- 大O、大Omega和大Theta描述了随着输入规模增加，资源使用增长的速度，抽象掉常数和低阶项，从而实现算法的独立于机器的比较。
- 可处理性与NP完全性
- 在多项式时间内可解决的问题被认为是可处理的；NP完全问题是所有NP中的问题都可以归约到的问题，如果能为其中任何一个找到多项式算法，则所有问题都将解决，这是一个悬而未决的问题（P对NP）。
Clinical relevance
算法分析指导着关于使用哪种算法或数据结构的每一个工程决策，预测系统如何随数据增长而扩展。认识到某个问题是NP难的，会促使实践者寻求近似、启发式或特殊情况方法，而不是精确的多项式算法，从而影响优化、调度和大规模计算等领域的工作。
History
渐近符号从解析数论引入计算机科学，并由Donald Knuth在20世纪60年代和70年代推广。NP完全性理论由Stephen Cook（1971）创立并由Richard Karp（1972）扩展，围绕可处理问题和难处理问题之间的界限重塑了算法设计。
Debates
- P对NP
- 所有解可以快速验证的问题是否也可以快速解决（P = NP）是理论计算机科学的核心开放问题；普遍推测P不等于NP，但尚无证明。
Key figures
- Donald Knuth
- Stephen Cook
- Richard Karp
- Robert Tarjan
Related topics
Seminal works
- cormen2009
- knuth1976bigo
- kleinberg2006
Frequently asked questions
- 最坏情况分析和平均情况分析有什么区别？
- 最坏情况分析限定了每种规模输入在最不利情况下的资源使用，提供了一个保证。平均情况分析估计了在输入分布下的预期资源使用，这可能更能代表典型性能，但取决于对输入分布的假设。
- 如果一个问题是NP完全的，是不是就无望解决了？
- 不是。NP完全性意味着在最坏情况下没有已知的有效算法，但实例通常可以通过近似算法、启发式方法、在实践中足够快的指数算法或利用特殊结构来解决。它预示着策略的改变，而非不可能。