多项式时间到底是什么？[复制]

Question

这个问题在这里已经有答案了：

• P、NP、NP-complete 和 NP-hard 的定义是什么？ 7 个答案

我试图理解算法的复杂性，很多算法都被归类为多项式。我在任何地方都找不到确切的定义。我认为复杂性不是指数级的。

线性/常数/二次复杂度算作多项式吗？如果能用简单的英语回答，我们将不胜感激:)

Answer 1

算法是多项式（具有多项式运行时间），如果对于$ k，c> 0 $，其在尺寸$ n $的输入上的运行时间最多为$ cn^k $。同等地，算法是多项式的，如果某些$ k> 0 $，其在尺寸$ n $的输入上的运行时间为$ o（n^k）$。这包括线性，二次，立方等。另一方面，具有指数运行时间的算法不是多项式。

两者之间有很多东西 - 例如，最著名的保理算法在时间$ o（ exp（cn^{1/3} log^{2/3} n）$中$;这样的运行时间被称为 亚指数. 。其他算法可能会在时间$ o（ exp（a log^c n））$上运行，对于某些$ a> 0 $和$ c> 1 $，这些被称为 准多项式. 。这样的算法最近已经 声称 对于较小的特征，用于离散日志。

Answer 2

运行算法可以占用一些计算时间。这主要取决于算法的复杂程度。计算机科学家已经根据其需要执行多少操作的行为来对算法进行分类（更多的操作需要更多的时间）。

其中一个显示了多项式时间的复杂性。即，操作复杂性与$ n^c $成正比，而n是输入的大小，C是一定的。显然，这个名字是由于$ n^c $而来的 多项式.

无论输入的大小如何，还有其他“类型”算法会占用恒定时间。有些占用$ 2^n $时间（是的，大多数时候真的很sllloolooww）。

我只是为外行简化了它，并可能引入了错误。因此，请阅读更多 https://stackoverflow.com/questions/4317414/polynomial time-and-pendential time

Answer 3

通俗地说，它是算法的运行时间。

算法的顺序（增长）可以是 Big-oh (O)、little-oh(o)、omega (Ω) 或 theta(θ)。

如果您在计算 RR 时遇到问题，请查看我之前提出的一些问题，如果您理解，请投票。

假设你有一个 for 循环：

 for(i=1 to n)
     x++

这段代码的顺序或时间复杂度是：在）

为什么要大哦？因为我们想要这段代码运行时最坏的情况。

请阅读此处（这些定义了算法的复杂性并告知您算法如何在多项式时间内完成）：

 http://en.wikipedia.org/wiki/NP_(complexity)

 http://en.wikipedia.org/wiki/NP-complete

 http://en.wikipedia.org/wiki/NP-hard

概括：

http://www.multiwingspan.co.uk/a23.php?page=types