什么是多项式时间算法 10

多项式时间在计算复杂性理论中，多项式时间是指问题的计算时间m（n）不大于问题大小n的多项式倍数。 任何抽象机器都有一个复杂度类，其中包括机器可以在多项式时间内解决的问题。

在数学中，整数因式分解（质因式分解）问题被赋予一个正整数，并写成几个除数的乘积。 例如，给定数字 45，它可以分解为 32 5。

根据算术的基本定理，这种分解的结果应该是唯一的。 这个问题在代数、密码学、计算复杂性理论和量子计算机等领域具有重要意义。

2005 年，RSA-200 作为公共研究的一部分，长度为 663 个二进制数字，已通过通用方法进行分解。

如果一个长度为 n 个二进制数字的大数是两个大小相等的除数的乘积，则没有好的算法将其分解为多项式时间复杂度。

这意味着没有已知的算法可以在 o（nk） （k 是常数）的时间内分解它。 但目前的算法也比（en）快。 换句话说，我们现在所知道的最好的算法比指数数量级时间快，比多项式数量级时间慢。

最著名的渐近线运行时间是普通数场筛选 （GNFS）。 时间是：

对于普通计算机来说，GNFS 是处理 n 个二进制数字近似的最知名方法。 然而，对于量子计算机，Peter Schauer 在 1994 年发现了一种算法，可以用来在多项式时间内解决这个问题。 如果建造一台大型量子计算机，它将对密码学产生重大影响。

该算法只需要 o（n3） 在良好的橙色时间和 o（n） 的空间。 构建这样的算法只需要 2n 个量子比特。 2001 年，第一台 7 量子比特量子计算机率先运行该算法，它分解了数字 15

如果您想获取最新消息，请前往维基百科，英文版。

定义：如果存在一个常数 c，使得对于所有 n>=0，则有 |f(n)|

要理解“伪多项式时间”，我们首先需要给出“多项式时间”的明确定义。

对于“多项式时间”，我们的直观概念是时间复杂度，其中是一个常数。 例如，选择排序的时间复杂度是多项式时间; TSP问题的蛮力求解的时间复杂度不是多项式时间。 我们将这种时间复杂度称为“传统时间复杂度”。

我们通常认为传统时间复杂度中的变量表示数据输入的大小。 例如，在排序的选择中，指示了数组中要排序的元素数。 图中的节点数在 TSP 问题中表示。 然而，这些所谓的输入量表只是直观的定义，不够严格。

为了对这些值进行归一化，我们在计算标准时间复杂度时给出了输入大小的标准定义：

问题中输入的大小是保存输入数据所需的位数。

例如，如果排序算法的输入是 32 位整数数组，则输入大小是指数组中的元素数。 对于具有节点和边的图形，所需的位数为 。

考虑到输入大小的定义，让我们看一下“多项式时间”的标准定义：

对于一个问题，如果一个算法能够在输入尺度 x 的情况下在 o（） 时间内解决问题，那么我们称该算法为多项式时间，其中是一个常数。

当我们处理一些图论、链表、数组、树等时，这个标准定义的多项式时间与我们传统的多项式时间没有太大区别。 例如，当对具有一系列元素的数组进行排序时，传统的时间复杂度为 。 因此，输入刻度，得到的标准时间复杂度仍然是多项式时间。

那么可以说 m（n） = o（n k），这是一个常数（取决于问题）。