计算机科学中一个核心问题的介绍
为什么最短路径问题容易解决，而旅行推销员问题却不容易？这其中的数学思想是什么？如何确定一个问题在规模增大时是否需要大量的步骤来解决？在本文中，您将学习有关这个主题的基础知识。如果您想深入研究这个问题，我在文章末尾还附上了与该主题相关的一个千禧年大奖问题的简短说明。
在我们开始讨论NP难度之前，您应该了解时间复杂度的基础知识。如果您熟悉时间复杂度、大O符号和最坏情况分析，可以跳过以下部分。
时间复杂度
当我们使用计算机并编写程序时，我们经常遇到可以用不同方法解决的问题。我们需要考虑的一个重要因素是这些解决方案的效率如何。时间复杂度帮助我们理解算法在解决的问题规模增大时运行的速度有多快。
大O符号可以类比为给算法贴上一个简单的标签，告诉我们算法完成所需的时间，基于我们处理的事物的数量。它是一种描述算法的步骤数如何相对于问题的输入规模增长的方式。
注意：时间复杂度实际上与您所采取的步骤数有关，而不是实际时间，所以这个命名有点不准确。否则，您可以使用更快的计算机和相同的算法。
我们通常关注最坏情况，因为我们希望确保无论给算法什么样的输入，它都不会花费超过一定时间。这有助于确保我们的解决方案在困难情况下也是可靠的。