时间复杂度转载自维基百科3_alittlewhitea的博客

维基百科，自由的百科全书. 在计算机科学中，算法的时间复杂度是一个函数，它 ... 冒泡排序、插入排序 ... 例如，矩阵链排序可以通过一个PRAM模型. 时间复杂度转载自维基百科3 alittlewhitea 于 2016-08-0415:58:35 发布 812 收藏 分类专栏： 笔记 文章标签： 维基百科 时间复杂度 算法 笔记 专栏收录该内容 6篇文章 0订阅 订阅专栏 时间复杂度 维基百科，自由的百科全书 在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。

这是一个关于代表算法输入值的字符串的长度的函数。

时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。

使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。

举例，如果一个算法对于任何大小为{\displaystylen}的输入，它至多需要{\displaystyle5n^{3}+3n}的时间运行完毕，那么它的渐近时间复杂度是{\displaystyleO(n^{3})}。

计算时间复杂度的过程，常常需要分析一个算法运行过程中需要的基本操作，计量所有操作的数量。

通常假设一个基本操作可在固定时间内完成，因此总运行时间和操作的总数量最多相差一个常量系数。

有时候，即使对于大小相同的输入，同一算法的效率也可能不同。

因此，常对最坏时间复杂度进行分析。

最坏时间复杂度定义为对于给定大小{\displaystylen}的任何输入，某个算法的最大运行时间，记为{\displaystyleT(n)}。

通常根据{\displaystyleT(n)}对时间复杂度进行分类。

比如，如果对某个算法有{\displaystyleT(n)=O(n)}，则称其具有线性时间。

如有{\displaystyleT(n)=O(2^{n})}，则称其具有指数时间。

目录   [隐藏]  1常见时间复杂度列表2常数时间3对数时间4幂对数时间5次线性时间6线性时间7线性对数（准线性）时间8多项式时间 8.1强多项式时间与弱多项式时间8.2复杂度类9超越多项式（superpolynomial）时间10准多项式时间 10.1与NP完全问题的关系10.2第一定义10.3第二定义 10.3.1指数时间假设11指数时间12双重指数时间13参见14参考资料 常见时间复杂度列表 更多资料： 数学运算的计算复杂度 以下是一些常见时间复杂度的例子。

名称复杂度类运行时间（{\displaystyleT(n)}）运行时间举例算法举例常数时间 {\displaystyleO(1)}10判断一个二进制数的奇偶反阿克曼时间 {\displaystyleO(\alpha(n))} 并查集的单个操作的平摊时间迭代对数时间 {\displaystyleO(\log^{*}n)} en:Cole-Vishkinalgorithm对数对数时间 {\displaystyleO(\log\logn)} 有界优先队列的单个操作[1]对数时间DLOGTIME{\displaystyleO(\logn)}{\displaystyle\logn}，{\displaystyle\logn^{2}}二分搜索幂对数时间 {\displaystyle(\logn)^{O(1)}}{\displaystyle(\logn)^{2}} （小于1次）幂时间 {\displaystyleO(n^{c})}，其中{\displaystyle0 0{\displaystyleO(2^{(\logn)^{\log\logn}})}Assumingcomplexitytheoreticconjectures, BPP iscontainedinSUBEXP.[2]次指数时间（第二定义） 2o(n）2n1/3Best-knownalgorithmfor integerfactorization and graphisomorphism指数时间E2O(n)1.1n,10n使用动态规划解决旅行推销员问题阶乘时间 O(n!)n!通过暴力搜索解决旅行推销员问题指数时间EXPTIME2poly(n)2n,2n2 双重指数时间2-EXPTIME22poly(n)22nDecidingthetruthofagivenstatementin Presburgerarithmetic 常数时间 主条目： 常数时间 若对于一个算法，{\displaystyleT(n)}的上界与输入大小无关，则称其具有常数时间，记作{\displaystyleO(1)}时间。

一个例子是访问数组中的单个元素，因为访问它只需要一条指令。

但是，找到无序数组中的最小元素则不是，因为这需要遍历所有元素来找出最小值。

这是一项线性时间的操作，或称{\displaystyleO(n)}时间。

但如果预先知道元素的数量并假设数量保持不变，则该操作也可被称为具有常数时间。

虽然被称为“常数时间”，运行时间本身并不必须与问题规模无关，但它的上界必须是与问题规模无关的确定值。

举例，“如果a>b则交换a、b的值”这项操作，尽管具体时间会取决于条件“a>b”是否满足，但它依然是常数时间，因为存在一个常量t使得所需时间总不超过t。

以下是一个常数时间的代码片段： intindex=5; intitem=list[index]; if(conditiontrue)then performsomeoperationthatrunsinconstanttime else performsomeotheroperationthatrunsinconstanttime fori=1to100 forj=1to200 performsomeoperationthatrunsinconstanttime 如果{\displaystyleT(n)=O(c)}，其中{\displaystylec}是一个常数，这记法等价于标准记法{\displaystyleT(n)=O(1)}。

对数时间 主条目： 对数时间 若算法的T(n)= O(log n)，则称其具有对数时间。

由于计算机使用二进制的记数系统，对数常常以2为底（即log2 n，有时写作lg n）。

然而，由对数的换底公式，loga n和logb n只有一个常数因子不同，这个因子在大O记法中被丢弃。

因此记作O（log n），而不论对数的底是多少，是对数时间算法的标准记法。

常见的具有对数时间的算法有二叉树的相关操作和二分搜索。

对数时间的算法是非常有效的，因为每增加一个输入，其所需要的额外计算时间会变小。

递归地将字符串砍半并且输出是这个类别函数的一个简单例子。

它需要O（logn）的时间因为每次输出之前我们都将字符串砍半。

这意味着，如果我们想增加输出的次数，我们需要将字符串长度加倍。

//递归输出一个字符串的右半部分 varright=function(str) { varlength=str.length; //辅助函数 varhelp=function(index) { //递归情况：输出右半部分 if(index>n; for(inti=1;i<=n;i=i*2) { cout<... zolalad baixingkuan for x . crankz weixin_45720714 qq_43638735 inti="3;//执行1次" while i="i+3;" s="s" android firefly_2002 a eg: weixin_40136018 eirlys ... onemoreoffer alittlewhitea csdn>