tem*_*def 93 algorithm big-o time-complexity
什么是假多项式时间？它与多项式时间有何不同？在伪多项式时间运行的一些算法具有运行时间,如O(nW)(对于0/1背包问题)或O(√n)(对于试验除法); 为什么不算作多项式时间？
tem*_*def 233
为了理解多项式时间和伪多项式时间之间的差异,我们需要从形式化"多项式时间"的含义开始.
多项式时间的常见直觉是" 某些k的时间O(n k)".例如,选择排序在时间O(n 2)中运行,这是多项式时间,而强力求解TSP需要时间O(n·n!),这不是多项式时间.
这些运行时都引用一些跟踪输入大小的变量n.例如,在选择排序中,n指的是数组中元素的数量,而在TSP中,n指的是图中的节点数.为了标准化"n"在此上下文中实际含义的定义,时间复杂度的形式定义定义了问题的"大小",如下所示:
问题输入的大小是写出该输入所需的位数.
例如,如果排序算法的输入是32位整数的数组,则输入的大小为32n,其中n是数组中的条目数.在具有n个节点和m个边的图中,输入可以被指定为所有节点的列表,后面是所有边的列表,这将需要Ω(n + m)位.
根据这个定义,多项式时间的形式定义如下:
如果算法的运行时间为某个常数k的O(x k),则算法在多项式时间内运行,其中x表示给予算法的输入的位数.
使用处理图形,列表,树等的算法时,此定义或多或少与传统定义一致.例如,假设您有一个排序算法,可以对32位整数数组进行排序.如果使用类似选择排序的方法来执行此操作,则运行时(作为数组中输入元素数量的函数)将为O(n 2).但是n,输入数组中的元素数量对应于输入的位数？如前所述,输入的位数为x = 32n.因此,如果我们用x而不是n表示算法的运行时间,我们得到运行时为O(x 2),因此算法在多项式时间内运行.
类似地,假设您在图上进行深度优先搜索,这需要时间O(m + n),其中m是图中边的数量,n是节点数.这与给定的输入位数有什么关系？好吧,如果我们假设输入被指定为邻接列表(所有节点和边的列表),那么如前所述,输入位的数量将是x =Ω(m + n).因此,运行时将为O(x),因此算法在多项式时间内运行.
然而,当我们开始讨论对数字进行操作的算法时,情况就会崩溃.让我们考虑测试数字是否为素数的问题.给定数字n,您可以使用以下算法测试n是否为素数:
function isPrime(n):
for i from 2 to n - 1:
if (n mod i) = 0, return false
return true
那么这段代码的时间复杂度是多少？好吧,那个内循环运行O(n)次,并且每次都需要一些工作来计算n mod i(作为一个非常保守的上界,这当然可以在时间O(n 3)中完成).因此,该整体算法在时间O(n 4)中运行并且可能更快.
2004年,三位计算机科学家发表了一篇名为PRIMES的论文,在P中给出了一个多项式时间算法来测试一个数是否是素数.它被认为是一个里程碑式的结果 那有什么大不了的？我们不是已经有了多项式时间算法,即上面的算法吗？
不幸的是,我们没有.请记住,时间复杂度的形式定义将算法的复杂性作为输入位数的函数.我们的算法在时间O(n 4)内运行,但这是输入位数的函数？好吧,写出数字n需要O(log n)位.因此,如果我们让x是写出输入n所需的位数,则该算法的运行时间实际上是O(2 4x),这不是 x中的多项式.
这是多项式时间和伪多项式时间之间区别的核心.一方面,我们的算法是O(n 4),它看起来像一个多项式,但另一方面,在多项式时间的形式定义下,它不是多项式时间.
为了直观了解算法不是多项式时间算法的原因,请考虑以下内容.假设我希望算法必须做很多工作.如果我写出这样的输入:
10001010101011
那么完成后需要一些最坏情况的时间T.如果我现在在数字的末尾添加一个位,如下所示:
100010101010111
运行时现在(在最坏的情况下)是2T.我可以通过增加一点来使算法的工作量增加一倍!
如果运行时是输入的数值中的某个多项式,而不是表示它所需的位数,则算法在伪多项式时间运行.我们的主要测试算法是假多项式时间算法,因为它在时间O(n 4)运行,但它不是多项式时间算法,因为作为写出输入所需的位数x的函数,运行时是O (2 4x)."PRIMES在P中"论文的原因是如此重要,因为它的运行时间(大致)为O(log 12 n),它作为位数的函数是O(x 12).
那为什么这很重要？那么,我们有许多伪多项式时间算法来分解整数.然而,从技术上讲,这些算法是指数时间算法.这对于加密非常有用:如果要使用RSA加密,则需要能够相信我们不能轻易地对数字进行因子分析.通过将数字中的位数增加到一个巨大的值(例如,1024位),您可以使伪多项式时间因子分解算法必须花费的时间量变得如此之大,以至于将完全且完全不可行的因素考虑在内.数字.另一方面,如果我们可以找到多项式时间因子分解算法,则不一定是这种情况.添加更多位可能会导致工作量大幅增长,但增长只会是多项式增长,而不是指数级增长.
也就是说,在许多情况下,伪多项式时间算法非常精细,因为数字的大小不会太大.例如,计数排序具有运行时O(n + U),其中U是数组中的最大数字.这是伪多项式时间(因为U的数值需要写出O(log U)位,因此运行时在输入大小中是指数的).如果我们人为地约束U使得U不是太大(例如,如果我们让U为2),则运行时为O(n),实际上是多项式时间.这就是基数排序的工作原理:通过一次处理一位数,每轮的运行时间为O(n),因此整个运行时间为O(n log U).这实际上是 写多项式时间,因为写出n个数来排序使用Ω(n)位,log U的值与写出数组中最大值所需的位数成正比.
希望这可以帮助!