我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:六合报码室 > 多项式时间 >

什么是伪多项式时间算法

归档日期:04-19       文本归类:多项式时间      文章编辑:爱尚语录

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  展开全部想要理解“伪多项式时间”,我们需要先给出“多项式时间”的一个清楚的定义。

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

  我们通常认为传统时间复杂度中的变量表示数据的输入规模。比如,选择排序中,指待排序数组中元素的个数;TSP问题中表示图中节点的数量。但是,这些所谓的输入规模,仅仅是直观的定义,并不足够严谨。为了标准化这些,在计算标准时间复杂度时,我们给出了输入规模的标准定义:

  比如,如果排序算法的输入是一个32-bit整数 数组,那么输入规模就是,是指数组中元素的个数。对于一个带有个节点、条边的图,需要的bit位数就是。

  对于一个问题,在输入规模为x的情况下,如果一个算法能够在O()时间内解决此问题,则我们称此算法是多项式时间的,其中为一常数。

  当我们处理一些图论、链表、数组、树等问题时,这个标准定义下的多项式时间和我们传统的多项式时间相差无几。比如,用选择排序对元素个数为的数组进行排序时,传统时间复杂度为。输入规模,因此,得到的标准时间复杂度是,仍然是多项式时间。

  类似的,假设在带有个节点、条边的图中做DFS(深度优先搜索),传统时间复杂度为。数据规模,因此,标准时间复杂度是,仍是多项式时间的。

  然而,当我们处理一些与数论有关的问题时,事情就不太乐观了。现在我们来讨论判断一个整数是否为素数的算法,下面是一个简单的算法:

  显然,这个算法在传统时间复杂度计算方法中是多项式时间的。我们不妨认为它的传统时间复杂度是。然后我们再来分析这个问题的输入规模,可能有的同学会说,对于32-bit整数,这个输入规模不就是32吗?这话虽然没错,但是因为在这个问题中,输入规模完全依赖于的大小,所以的范围不再限制在32-bit整数的范围内,而是要探讨当更大时对数据规模的影响。我们知道,保存一个整数所需要的bit位数,因此,在标准的时间复杂度中,此算法的复杂度变为了!这已经不再是多项式时间,而是一个指数时间。

本文链接:http://barstaffuk.com/duoxiangshishijian/101.html