时间复杂度计算
时间复杂度计算
时间复杂度计算
学习数据结构时，觉得时间复杂度计算很复杂，怎么也看不懂，差不多三年之后，还是不懂，马上就要找工作了，赶紧恶补一下吧：
首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。
当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。
此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。
常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。
1. 大O表示法
设一个程序的时间复杂度用一个函数 T(n) 来表示，对于一个查找算法，如下：int seqsearch( int a[], const int n, const int x){int i = 0;for (; a[i] != x && i & i++ );if ( i == n) return -1;}这个程序是将输入的数值顺序地与数组中地元素逐个比较，找出与之相等地元素。在第一个元素就找到需要比较一次，在第二个元素找到需要比较2次，……　，在第n个元素找到需要比较n次。对于有n个元素的数组，如果每个元素被找到的概率相等，那么查找成功的平均比较次数为:f(n) = 1/n (n + (n-1) + (n-2) + ... + 1) = (n+1)/2 = O(n)这就是传说中的大O函数的原始定义。
用大O来表述 要
全面分析一个算法，需要考虑算法在最坏和最好的情况下的时间代价，和在平均情况下的时间代价。对于最坏情况，采用大O表示法的一般提法（注意，这里用的是
“一般提法”）是：当且仅当存在正整数c和n0,使得 T(n) &= c*f(n)对于所有的n &= n0
都成立。则称该算法的渐进时间复杂度为T(n) = O(f(n))。这个应该是高等数学里面的第一章极限里面的知识。这里f(n) =
(n+1)/2, 那么c * f(n)也就是一个一次函数。就是在图象上看就是如果这个函数在c*f(n)的下面，就是复杂度为T(n) =
对于对数级，我们用大O记法记为O(log2N)就可以了。
规则1） 加法规则T(n,m) = T1(n) + T2(n) = O ( max (f(n), g(m) )2) 乘法规则T(n,m) = T1(n) * T2(m) = O (f(n) * g(m))3)一个特例在大O表示法里面有一个特例，如果T1(n) ＝ O?， c是一个与n无关的任意常数，T2(n) = O ( f(n) ) 则有T(n) = T1(n) * T2(n) = O ( c*f(n) ) = O( f(n) ).也就是说，在大O表示法中，任何非0正常数都属于同一数量级，记为O(1)。4)一个经验规则有如下复杂度关系c & log2N & n & n * Log2N & n^2 & n^3 & 2^n & 3^n & n!其中c是一个常量，如果一个算法的复杂度为c 、 log2N 、n 、 n*log2N ,那么这个算法时间效率比较高 ，如果是 2^n , 3^n ,n!,那么稍微大一些的n就会令这个算法不能动了，居于中间的几个则差强人意.
1）基本知识点：没有循环的一段程序的复杂度是常数，一层循环的复杂度是O(n),两层循环的复杂度是O(n^2)? （我用^2表示平方，同理 ^3表示立方）；
2）二维矩阵的标准差，残差，信息熵，fft2,dwt2,dct2的时间复杂度:
标准差和残差可能O(n)，FFT2是O(nlog(n))，DWT2可能也是O(nlog(n))；信息熵要求概率，而dct的过程和jpeg一样。因
为和jpeg一样,对二难矩阵处理了.Y=T*X*T'，Z=Y.*Mask，这样子,还有分成8*8子图像了;
3)example：
1、设三个函数f,g,h分别为 f(n)=100n^3+n^2+1000 , g(n)=25n^3+5000n^2 , h(n)=n^1.5+5000nlgn
请判断下列关系是否成立：
（1） f(n)=O(g(n))
（2） g(n)=O(f(n))
（3） h(n)=O(n^1.5)
（4） h(n)=O(nlgn)
这里我们复习一下渐近时间复杂
度的表示法T(n)=O(f(n))，这里的"O"是数学符号，它的严格定义是"若T(n)和f(n)是定义在正整数集合上的两个函数，则
T(n)=O(f(n))表示存在正的常数C和n0
,使得当n≥n0时都满足0≤T(n)≤C?f(n)。"用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常
数。这么一来，就好计算了吧。
◆ (1)成立。题中由于两个函数的最高次项都是n^3,因此当n→∞时，两个函数的比值是一个常数，所以这个关系式是成立的。
◆ （2）成立。与上同理。
◆ （3）成立。与上同理。
◆ （4）不成立。由于当n→∞时n^1.5比nlgn递增的快，所以h(n)与nlgn的比值不是常数，故不成立。
2、设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。
(1) i=1; k=0
while(i&n)
{ k=k+10*i;i++;
解答：T(n)=n-1， T(n)=O(n)， 这个函数是按线性阶递增的。
(2) x=n; // n&1
while (x&=(y+1)*(y+1))
解答：T(n)=n1/2 ，T(n)=O(n1/2)，最坏的情况是y=0，那么循环的次数是n1/2次，这是一个按平方根阶递增的函数。
(3) x=91; y=100;
while(y&0)
{x=x-10;y--;}
解答： T(n)=O(1)，这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n没有? 没。这段程序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数。
同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。1、时间复杂度（1）时间频度一
个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间
多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语
句执行次数称为语句频度或时间频度。记为T(n)。（2）时间复杂度在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。一
般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大
时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n))
为算法的渐进时间复杂度，简称时间复杂度。在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...，k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。2、空间复杂度与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作:S(n)=O(f(n))我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。
（3）渐进时间复杂度评价算法时间性能　　主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。【例3．7】有两个算法A1和A2求解同一问题，时间复杂度分别是T1(n)=100n2，T2(n)=5n3。（1）当输入量n＜20时，有T1(n)＞T2(n)，后者花费的时间较少。（2）随着问题规模n的增大，两个算法的时间开销之比5n3/100n2=n/20亦随着增大。即当问题规模较大时，算法A1比算法A2要有效地多。它们的渐近时间复杂度O(n2)和O(n3)从宏观上评价了这两个算法在时间方面的质量。在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。【例3．8】算法MatrixMultiply的时间复杂度一般为T(n)=O(n3)，f(n)=n3是该算法中语句(5)的频度。下面再举例说明如何求算法的时间复杂度。【例3．9】交换i和j的内容。&&&&& Temp=i;&&&&& i=j;&&&&& j=　　以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。&&&&& 如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。【例3．10】变量计数之一。(1) x=0;y=0;(2) for(k-1;k&=n;k++)(3)&&&& x++;(4) for(i=1;i&=n;i++)(5)&&&&&& for(j=1;j&=n;j++)(6)&&&&&&&& y++;　　一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分。因此，以上程序段中频度最大的语句是(6)，其频度为f(n)=n2，所以该程序段的时间复杂度为T(n)=O(n2)。　　当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。【例3．11】变量计数之二。(1) x=1;(2) for(i=1;i&=n;i++)(3)&&&&&& for(j=1;j&=i;j++)(4)&&&&&&&&&& for(k=1;k&=j;k++)(5)&&&&&&&&&&&&&& x++;　　该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句(5)的执行次数：则该程序段的时间复杂度为T(n)=O(n3/6+低次项)=O(n3)。（4）算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。【例3．12】在数值A[0..n-1]中查找给定值K的算法大致如下：&&&(1)i=n-1;&&&&&&&&& (2)while(i&=0&&(A[i]!=k))&&&&& (3)&&&& i--;&&&&& (4)&&&&& 此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关:①若A中没有与K相等的元素，则语句(3)的频度f(n)=n；②若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。（5）最坏时间复杂度和平均时间复杂度　　最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。&&&&& 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。【例3．19】查找算法【例1·8】在最坏情况下的时间复杂度为T(n)=0(n)，它表示对于任何输入实例,该算法的运行时间不可能大于0(n)。&&&&& 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。&&&&& 常见的时间复杂度按数量级递增排列依次为：常数0(1)、对数阶0(log2n)、线形阶0(n)、线形对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、…、k次方阶0(nk)、指数阶0(2n)。显然，时间复杂度为指数阶0(2n)的算法效率极低，当n值稍大时就无法应用。&&&&& 类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。算法的时间复杂度和空间复杂度合称为算法的复杂度。
发表评论：
TA的最新馆藏数据结构作业解答_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
数据结构作业解答
上传于||文档简介
&&数​据​结​构​的​一​些​题​目​解​答
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
下载文档到电脑，查找使用更方便
还剩10页未读，继续阅读
你可能喜欢算法的时间复杂度_百度知道
算法的时间复杂度
例 n＋2log2n。它的时间复杂度怎么算？
6n∧2－12n＋1的时间复杂度、n（n＋1）（n＋2）╱6的时间复杂度和2∧（n＋1）＋100n的时间复杂度
提问者采纳
f(n)=a1*n^m+a2*n^(m-1)+.;=3*2^n=3*g(n)==&T(n)=O(n^2)(3)n(n+1)(n+2)&#47，这样就有T(f(n))=O(g(n));=n0=2时)&lt以下是考研时常用的计算方法.;=n0=4)=2*g(n)===&gt，实际上最简单的方法采用多项式最大阶的方法.an-1*n+an的时间复杂度为.，如;=6n^2-n^2(n&gt..,简称为T(n)=O(g(n))因此.;=2*2^n+n*2^7&=n^3+4n^2(n&gt，找一个函数g(n);=n+2n=3n=3*g(n)==&gt:(1)f(n)=n+2log2n&T(n)=O(n^3)(4)2^(n+1)+100n&=2n^3(n&gt,找一个自然数n0;=12)=7n^2=7*g(n)==&=n(n+1)(n+2)=n(n^2+3^n+2)=n^3+3n^2+2n&6&lt,使f(n)&T(n)=O(n)(2)6n^2-12n+1&=n0*g(n):T(f(n))=O(n^m)采用时间步法
其他类似问题
为您推荐：
其他2条回答
O(nlog2n)6n^2 - 12n + 1 ===&gt时间复杂度就是n趋于无穷大时无穷大的最大阶次所以; O(n^2)n(n+1)(n+1)/6 ===& O(n^3)2^(n+1) + 100n ===&gt：n + n log2n
在算法中，不能准确得算出需要多少次运算，所以，若存在多种阶段的多项式如： n＋2log2n+6n∧2时，所取的时间复杂度是按照最高阶的来算的即：在n＋2log2n中，它的时间复杂度是O(n)
因为n的增长速率比logn的增长速率快，所以可以把2log2n省去
n，2n，3n...的时间复杂度都是O(n)，即可把变量前面的系数省去
同理：6n∧2和n∧2的时间复杂度都是O(n∧2)
下面是部分增长速率的级别分析：
logn，n，n∧2，n∧3....2∧n...
按照上面的方法：
6n∧2－12n＋1的时间复杂度相当于n∧2－n＋1，取得最高阶的项，即为时间复杂度：O(n^2)
所以n（n＋1）（n＋2）╱6的时间复杂度为O（n^3）
此时可看为n*m*k，可看为n^3
2∧（n＋1）＋100n的为O(2^n)
----------
您可能关注的推广
时间复杂度的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁怎么评价一个算法的效率？
* 假如两个算法的时间复杂度都是O(n)，是不是应该考虑n之前的系数？* 假如A算法需要做1000次比较，100次赋值；算法B需要做500次比较，200次除法，200次赋值。那么哪种算法效率高？不同的步骤（赋值/加减/乘除/比较/空间占用）的复杂度如何进行比较和评判？* 评价算法一般是考虑平均复杂度（或者针对某类问题的平均复杂度），如果通过实际测试来评价算法的效率，是不是有说服力？
按投票排序
我觉得， 最简单直接的办法， 是考察算法在特定条件下（时间、空间、其他开销、特定的计算机、特定的输入）解决问题的能力：能解决， 那么这个算法就是可行的；不能解决， 那么这个算法就是白搭。如果要找寻通用的评价方法， 也应该根据算法的平均时间复杂度平均空间复杂度最坏时间复杂度最坏空间复杂度输入与时间开销的分布关系特定输入下的时间空间开销所用的资源开销（如并行处理）算法运行的特殊要求（如硬件支持）来综合判断，不能一概而论。
复杂度是衡量性能的主要标准，但也不是唯一标准。主要是要对数据量有一个相对准确的估算。画一个图，横坐标是数据量，纵坐标是时间。复杂度高的斜率高，复杂度低的斜率低，而当复杂度低的系数高时，这两个算法的曲线在第一象限一定有一个交点。那么到底选择哪个算法，在于你的数据量在这个交点的左边还是右边。如果可以预估到，绝大多数时候数据量都在左边，那完全可以选择复杂度高的算法。但如果不太确定数据量，要相信数据量总会增大的，所以选择复杂度低的算法扩展性更强。举个例子，我们经常要对某学校的几千名学生的某项数据进行排序(假设数据范围非常大，1～10亿)。程序员选择了两个算法：1、快速排序，O(nlgn)2、位图排序，O(n)前者复杂度低，但开辟内存非常快。几千名学生瞬间就排好了。后者复杂度到了极限，但该算法要开辟数据范围/8Byte的内存，开辟内存和初始化本身就需要几秒的时间，实际执行的操作比快排多非常多，而且每次排序服务器的内存都被占满了。那么我们选择哪个？必然前者，因为可以估算得出，该学校的学生十年内也不会超过1万人。但如果这个系统以后会用来统计全球所有人的该项数值，那么后者算法更合适。
评价单个算法，往往是通过将其与另外一个算法进行比较。一般分为理论上与实践中两方面来评价一个算法的效率。理论上，大O记号是一个上界，通常可以在一定程度上反应算法的真实效率。该思想基于如下考虑：如果算法A1在“最坏情况”下比算法A2要好，那么认为A1好于A2。这里特指“最坏情况”，而并非所有情况，即有时候A2反而会好于A1，比如希尔排序在n比较小的时候通常好于快速排序。算法的时间空间开销往往和问题规模成正比，所以“最坏情况”，实际上指的是当问题规模趋近于无穷的时候。因此通常在理论上认为，一个复杂度为O(n^1.68)的算法，是好于一个复杂度为O(n^2)的算法的，而与算法中n前面的系数无关。特别说明的是，大O记号只是理论上其中一种衡量上界的标准，而这个界并非是严格紧致的，例如一个n^2复杂度的算法也可以说它是O(n^3)的。而反应上下界的大Θ记号就要相对准确些。实际使用中，用大O记号一般都默认用的是该算法所有可能上界中的最下界。相比与时间复杂度，空间复杂度往往不太过追求，甚至为了更低的时间复杂度去牺牲空间复杂度，即“用空间换时间”。这是由于随着计算机硬件的发展，算法中数据的存储往往不是太大问题，一般都考虑“谁用的时间更少”，而非“谁用的空间更小”。当然，在时间复杂度一样的情况下，会去追求空间复杂度，比如原地归并排序(in place merge sort)就是个很好的例子。而在实践中，从实验上评价算法的效率，就要考虑很多额外的因素。1. 编码实现的效率由于算法最后的实现效率在很大程度上和编码实现方式有关，所以大家通常都会保证自己的实现方式尽量高效。比如用相对高效的语言（例如C）来实现、将递归算法进行非递归改写、结合编译器做代码上的优化等等。这样一来，实现手段上的不同难免会给算法真实效率上的评价带来影响。比如一个很好实现的O(n^3)的算法，的确有可能比一个相对差的实现的O(n^2)的算法要快。但是，大O记号的魅力就在于，当n足够大的时候，算法复杂度上带来的差异一定可以抹平不同实现方式上的差异——一个O(n^2)的算法最终(n大于某个值时)一定是比O(n^3)的算法要快的。2. 机器硬件的影响在不同计算机硬件上运行显然会对算法运行时间带来影响，通常会指明运行的机器操作系统，CPU类型、主频等参数，从而方便比较。比如算法A1运行的机器比A2运行的机器差不多快一倍，那么比较时间的时候就对应地将A2的运行时间乘以二分之一。一般很难在不同硬件上做到精确的比较，只能大概而为之。即使在同一台机器上进行比较，也和编译时的参数设置，编译器不同有关，比如gcc中O2可能会比O3快、intel芯片上用icc编译的代码通常比gcc编译的要快等等，影响因素太多，无法做到精确。这里，要格外说明的一点是cache命中率的问题。由于CPU缓存和内存读取速度上的巨大差异，cache的命中率过低往往会严重影响算法真实性能的比较。这方面一个比较经典的例子就是堆排序，可以参考知乎上 问题中的高票回答。另，数据结构的设计也会影响算法这方面的性能。此外，如果是在多核环境或者机群上运行，不同CPU的缓存之间会互相影响命中率的情况也应加以考虑并尽量避免。3. benchmark测试为了更客观公正的比较算法的真实效率，学术界(包括某些工业界)的做法是建立一个公认的针对某问题的算法测试数据集，也称为benchmark(见过翻译为“算法试金石”的，觉得很形象)。通常的做法是在给定问题的benchmark上，给定一个时间上限，运行不同的算法，通过比较结果来评价算法效率。这里比较的标准一般有两条，解的质量和求解速度，前者更为本质。例如，在benchmark的100个问题中，每个问题给定7200秒的时间上限，算法A1求解出了90个，平均时间100秒；算法A2求解出了70个，平均时间60秒——一般认为A1好于A2。这是因为A2求解速度上的优势可能和实现手段运行环境多方面因素有关；但是否能解出问题，更能反映算法的本质。除了统计平均值，还有一种是统计median值(中位数/中值)。在上面的例子中，A1所解出的90个平均花费100秒，但有可能是其中70个算例花费时间都小于60秒，只是其中某几个算例花费很多时间才解出，从而拖高了平均值，显然A1是全面好于A2的。此时平均时间就不是一个好的刻度，而median会更合适。比如比较A1、A2分别算出的算例中的median时间；或者比较总共100个算例的median时间，即看算出50个算例A1、A2的平均花费时间。诸如此类的统计方式很多，不一一详述。但大体原则是，解的质量为主，求解速度为辅。此外，对于随机化算法，还需要根据不同随机种子上的不同运行情况来求平均值来进行比较，比如100个算例集，每个都用不同的随机种子运行100次，再统计平均时间，平均成功率等等。这种规模的试验计算量往往比较大，需要用到机群，但结果比较具有说服力。总结有些算法的复杂度，难以从理论上给出定量分析，通常是以benchmark上的算法实际效率比较为主；而可以定量分析出复杂度优劣的算法，在实际应用中，也会受到多方面因素的影响，benchmark上的实验结果往往更具有说服力。实际上，基于合理的benchmark的实验性比较和理论上的分析是完全一致的。因为无论是实现手段、还是运行环境等多方面因素带来的影响，充其量只能影响算法客观复杂度里n前面的系数。这种差距，会随着问题规模的增长而被算法复杂度上的差异所抹平——当然，这需要新的算法能有效抓住问题本质，带来足够大的改进才行。希望有所帮助，欢迎讨论。
我认为这里其实有两个问题，一个是算法的时间复杂度，另一个是算法实现后的执行效率。在两个算法的平均时间复杂度相近的情况下，系数是需要考虑的，同时还要考虑实际情况下最坏情况和最好情况出现的可能性，以及对于n较大时和n较小时的算法时间复杂度的比较。算法的执行效率相对来说属于实现的问题，和硬件架构有关，不同运算指令的比较经常用指令执行需要消耗的时钟周期来衡量。
* 当然应该考虑系数* 不同的指令在不同的CPU架构上效率不同, 因此不能一概而论, 需要通过实际测试来决定.
评价一个算法的效率，一般有两种大致的思路：看代码，找出关键操作，推导出该操作执行次数关于输入规模的变化函数，并且一般找出最大项作为其时间复杂度大O表示迭代，使用“doubling ratio experiments”迭代出大致的增长率
Big-O notation旨在描述一个算法执行步骤的一个增长曲线，而非具体的执行时间。事实上在数据规模一定小的情况下，更高复杂度的算法，可能执行速度更快。 举例来说，图中的两个函数，在数据范围足够小的情况下，O(n^2)的效率会更好。图中的两个函数，在数据范围足够小的情况下，O(n^2)的效率会更好。如果我们把，数据扩大10倍再来看，当数据量超过一个值c的时候，常数所起到的影响就已经微乎其微了。当数据量超过一个值c的时候，常数所起到的影响就已经微乎其微了。楼上的
的答案中谈到，一般比较确定环境下的平均执行时间。比如O(n)的基排一般都比O(n*log(n))的排序慢很多。基排的单步操作可能要更耗时，但是终归是复杂度以下的函数或者常数。当n的值达到某一个常数c后，O(n log (n)) 的效率总是会高于O(n)的，只是对数级函数增长的慢到，现实遇到的问题中都没有超过这个常数而已。比如我们加上一个n log n的函数，这么看起来，总是要比线性的要差啊，把数据再翻上10倍，这里，n log n 已经明显要比线性 n 的效率低了，而且这里，n log n 已经明显要比线性 n 的效率低了，而且随着数据量的增大会越来越差。不论所谈论的常数多大，总会在那么一个点开始变的越来越差。实际应用中在有些分治的问题上，不同的数据规模下，可能会使用不同复杂度的算法，比如用更高复杂度的算法去处理边界上小规模数据。像题主描述的问题中，如果知道数据规模，自然可以通过这个评价方法，综合考量时间、空间以及编写代码的难度，选取一个更合适的算法。
Big O可以用来表示增长情况，算法负责度。对于第一个问题，Big O 指的是当输入的量非常大的时候复杂度的增加速度，所以如果是一个常数，当输入趋向无穷时可以忽略。对于前面的系数，比如2n，3n或1000n，将他们和指数增长比，无论是几，当n很大时指数将远大于幂函数，所以n有一些影响，但是在Big O 中这是不予考虑的。第二个问题不可一概而论，一般可以将每一步近似看成一样的。但计算机在调取的时候数据会分层存储，实际会有差别。处理的方法是将每一步看成一样，一步就算一。如果有一个循环结构，这种情况才值得注意，因为一个循环结构可能运行1000次比较，这样的差距远比比较或除法的差距大，这是我们需要考虑的。对于第三个问题，理论上我们可以比较平均值，但实际上我们更关心最坏值。要知道理论值，我们得知道这种情况的概率分布，然后进行数学运算求解。这样的运算是非常复杂的，特别是对一个庞大的程序项目，几乎不可能得到。用实际测试法不现实，这里举两个原因。第一，如果一个程序要运行几年，怎么测试？谁能等得住？另外一点，输入值不同，程序运行的时间会相差很多，在不同性能电脑上也差别很大 不具有比较性。
上面说的都很有道理，不过有时候效率很难算出来，可以直接弄几个数据看看时间。
已有帐号？
无法登录？
社交帐号登录