为什么学习复杂性理论？

Question

我是在算法研究中的业余爱好者。有一段时间我有一个燃烧的问题，为什么我们在计算机科学中研究复杂性理论吗？我问的原因是因为具有更好的渐近复杂性的算法对于实际目的并不总是更快的速度，实际上它们可能是荒谬的速度。为什么不制定一个更适合科学研究和行业的实际需求的理论？

作为示例，已知开发算法以确定完美的国际象棋游戏可以在 $ o（1）$ 中完成，作为合法的数量在8×8网格上的国际象棋游戏是从上面界定的。但是，我已经听说过这个算法比宇宙的年龄需要更长的时间来终止。这引出了这个问题，为什么复杂的理论？在我看来，这个领域从根本上缺陷，计算机科学家应该使用更好的方法来研究算法。

（注意：我真诚地为该领域的研究人员道歉。☻）

Answer 1

这不是一个简单的问题，你不应该期待一个简单的答案。这个空间有一系列类似的问题：为什么我们研究渐渐的运行时间？为什么我们使用渐近运行时间分析来分析算法？为什么我们研究复杂性理论？每个人都有多个答案;我们这样做的不仅仅是一个原因，不同的人可能有不同的原因。

渐近运行时间分析具有优缺点。您已经准确地确定了一个缺点之一：良好的渐近运行时间并不能保证在实践中的良好运行时间。但是，如果你只专注于单一的优势或缺点，那么你就不会完整地了解这种分析风格的优势和弱点。一些优点在于，分析是相对易无的，它不是特定的特定架构，它提供了有关可伸缩性的有用信息，并且至少一些在识别算法瓶颈时具有有用的预测力的时间。例如， $ o（n ^ 2）$ 时间算法和a $ o（n \ log n ）$ 时间算法通常可以很重要，即使我们忽略了恒定因素。一些缺点是恒定因素可能是重要的，缓存和内存层次效应可能非常重要，但渐近运行时间分析忽略，（就像任何公制）完全优化渐近运行时间就可以导致荒谬的结果略微实用实用程序（见银河算法和 goodhart的法律）。

我认为检查替代方案也很有用。我鼓励您探索渐近运行时间分析的替代方案，并通过您所提出的替代方面的替代。如果您不尝试提出具体的提议，很容易假设它不能难以找到更好的东西......但是当您被迫提交具体的东西时，您可能会发现它是比预期更具挑战性。例如，我鼓励您熟悉Knuth对算法在 mix 中的算法运行时间的分析Taocp系列。他确实有混凝土运行时间分析，没有渐近学，考虑到恒定因素。如果您强制自己通过细节工作，您将迅速发现这一点：这是超级繁琐的，非常特定于特定的计算机架构，并且往往并不多的启发。

我们可以类似地讨论每个其他主题 - 例如，为什么或为什么不研究复杂性理论 - 而且你发现他们也有细微差别。

我也想突出你的理论和算法社区是一个广泛的工作，有一系列不同的工作风格。你似乎将它融入一堆一堆，但是有一定的工作：其中一些是超级理论和远处的实践，其中一些是由具体问题的高度实用和动机，并且可能会产生立即影响在极端之间的各个点都有一系列工作。我认为理解，在理论界有一些工作中的实际相关性或产生重大影响是很重要的，因为有更多的理论而不是近期影响的理论而产生了重大影响。

自从您要求专注于满足行业需求的理论框架以来，您也可能对感兴趣Word RAM 模型，缓存忘记算法，以及并行外部存储器型号。

我强烈建议您阅读以下资源，因为它们与您的问题密切相关：为什么多项式时间被称为“高效“？，解释了算法渐近复杂性与设计算法的实践的相关性，忽略大O 的恒定因子的理由。