注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Mr.Right

不顾一切的去想,于是我们有了梦想。脚踏实地的去做,于是梦想成了现实。

 
 
 

日志

 
 
关于我

人生一年又一年,只要每年都有所积累,有所成长,都有那么一次自己认为满意的花开时刻就好。即使一时不顺,也要敞开胸怀。生命的荣枯并不是简单的重复,一时的得失不是成败的尺度。花开不是荣耀,而是一个美丽的结束,花谢也不是耻辱,而是一个低调的开始。

网易考拉推荐

阿英讲算法的时间复杂度  

2012-05-02 00:33:54|  分类: 学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

即以此功德,庄严佛净土。上报四重恩,下济三途苦。惟愿见闻者,悉发菩提心。在世富贵全,往生极乐国。


首先了解一下几个概念。一个是时间复杂度,一个是渐近时间复杂度。前者是某个算法的时间耗费,它是该算法所求解问题规模n的函数,而后者是指当问题规模趋向无穷大时,该算法时间复杂度的数量级。


 


当我们评价一个算法的时间性能时,主要标准就是算法的渐近时间复杂度,因此,在算法分析时,往往对两者不予区分,经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度,其中的f(n)一般是算法中频度最大的语句频度。


 


定义:如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数 T(n)称为这一算法的“时间复杂性”。


当输入量n逐渐加大时,时间复杂性的极限情形称为算法的“渐近时间复杂性”。


我们常用大O表示法表示时间复杂性,注意它是某一个算法的时间复杂性。大O表示只是说有上界,由定义如果f(n)=O(n),那显然成立f(n)=O(n^2),它给你一个上界,但并不是上确界,但人们在表示的时候一般都习惯表示前者。          


此外,一个问题本身也有它的复杂性,如果某个算法的复杂性到达了这个问题复杂性的下界,那就称这样的算法是最佳算法。


“大O记法”:在这种描述中使用的基本参数是 n,即问题实例的规模,把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order),比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时,运行时间至多将以正比于 f(n)的速度增长。


这种渐进估计对算法的理论分析和大致比较是非常有价值的,但在实践中细节也可能造成差异。例如,一个低附加代价的O(n^2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然,随着n足够大以后,具有较慢上升函数的算法必然工作得更快。 

 

(一)常数阶时间复杂度O(1)

例1:

 Temp=I; i=j; j=temp;                     

 

以上三条单个语句的频度均为1,该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶,记作T(n)=O(1)。如果算法的执行时 间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。 


(二)二次时间复杂度O(n^2)


例2:双层for循环的时间复杂度是O(n^2),此例详细分析各个步骤的基本运算次数

    sum=0;                (1次运算)---- ①


for(i=1; i<=n; i++)      (1+2n+n*(3m+1)次运算)---- ②

       for(j=1; j<=m; j++) (3m+1次运算) ---


         sum++;       (1次赋值sum=sum+1 )

解:① 1次运算具体包含1次赋值sum=0,需要1小步执行出结果;


② 外层循环1+2n+n*(3m+1)次运算具体包括一次初始化赋值i=1;n次判断i<=n;n次执行循环体内的语句,而该循环体内有(3m+1)条子语句,故执行循环体内的语句总共需要n*(3m+1)次运算;n次i++自增运算


③ 内层循环3m+1次运算具体包含一次赋值j=1(仅仅初始化时执行1次),m次判断j<=m,m次计算表达式sum++,m次计算j++

④ 阿英注:①和②是在同一个等级的,注意体会下为什么总的运算次数为


1 + 2n + n*(3m +1) + 1!


T(n) = 3*m*n + 3*n + 2 = O(n*m),当m=n时,T(n) = O(n^2)。


⑤ 有疑惑的人,请继续看下面的原因,注意体会一切诸佛说的万法皆空,因果不空,缘起性空,真空妙有!


为什么m*n前面的系数3可以忽略?因为它不是主要矛盾,例如当m*n=300时,3*m*n=900; 当 m*n = 30000时, 3*m*n = 90000。


为什么3*m*n + 3*n + 2 中  3*n + 2 可以忽略? 因为它不是主要矛盾,例如当3*m*n = 9000,3*n+2 = 11,则9000与9000-11差别不大。


结论:对于时间复杂度为T(n)中对n的线性运算(加法和数乘)不影响时间复杂度!

 

例3:双层for循环的时间复杂度是O(n^2),不考虑线性运算时,简化而实用的时间复杂度计算方法

   for (i=1; i<n; i++)

   { 

       y=y+1;        ①   

       for (j=0;j<=(2*n);j++)    

          x++;        ②      

   }          

解:  ①的频度是n-1,实际上总共要1+3(n-1)次运算,但这里抓住主要矛盾就行了;

        ②的频度是(n-1)*(2n+1)=2n^2-n-1

        ③总的频度是 f(n)=2n^2-n-1+(n-1)=2n^2-2

         该程序的时间复杂度T(n)=O(n^2).         


(三)线性时间复杂度O(n)     

例4:单层循环的时间复杂度为线性时间复杂度O(n)

   a=0;   b=1;              ①

   for (i=1; i<=n; i++)  ②

   {  

      s=a+b;    ③

      b=a;     ④  

      a=s;     ⑤

   }

解:  ① 需要2步操作

      ② 需要1次赋值操作i=1,n次判断i<=n,执行③④⑤各需要n次,执行i++需要n次,for循环执行下来总共要5*n+1步

         T(n)=5*n+1+2=5n+3=O(n).


例5:设一个程序的时间复杂度用一个函数 T(n) 来表示,对于一个查找算法,如下: 


int seqsearch( int a[], const int n, const int x) 

int i = 0; 

for (; a[i] != x && i < n ; i++ ); 

if ( i == n) return -1; 

else return i; 

这个程序是将输入的数值顺序地与数组中地元素逐个比较,找出与之相等地元素。 


在第一个元素就找到需要比较一次,在第二个元素找到需要比较2次,…… ,在第n个元素找到需要比较n次。对于有n个元素的数组,如果每个元素被找到的概率相等均为1/n,那么查找成功的平均比较次数为: 


f(n) = 1/n (n + (n-1) + (n-2) + ... + 1) = (n+1)/2 = O(n) 

                                                                                                  

(四)对数时间复杂度O( log2(n) )


例6:

    i=1;       ①

   while (i<=n)

      i=i*2; ②

解: 语句1的频度是1,  

       设语句2的频度是f(n),  则:2^f(n)<=n; f(n)<=log2(n)

       取最大值f(n)= log2(n)

         T(n)=O( log2(n) )

 

 (五)立方时间复杂度O(n^3)


例6-1:三重循环的时间复杂度为O(n^3)

  (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)的执行次数:当i=m时, j 可以取 0,1,...,m-1 ,  所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次;所以,i从0取到n, 则循环共进行了0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6,则该程序段的时间复杂度为T(n)=O(n3/6+低次项),所以时间复杂度为O(n^3)。


例6-2:求两个n阶方阵的乘积 C=A×B,其算法如下:

# define n 100 // n 可根据需要定义,这里假定为100

void MatrixMultiply(int A[a],int B [n][n],int C[n][n])

{ //右边列为各语句的频度

int i ,j ,k;

(1) for(i=0; i<n;j++) n+1

(2)     for (j=0;j<n;j++) { n(n+1)

(3)       C[i][j]=0; n2

(4)       for (k=0; k<n; k++) n2(n+1)

(5)         C[i][j]=C[i][j]+A[i][k]*B[k][j]; n3

         }

       }

    该算法中所有语句的频度之和(即算法的时间耗费)为:

           T(n)=2n3+3n2+2n+1 

分析:

   语句(1)的循环控制变量i要增加到n,测试到i=n成立才会终止。故它的频度是n+1。但是它的循环体却只能执行n次。语句(2)作为语句(1)循环体内的语句应该执行n次,但语句(2)本身要执行n+1次,所以语句(2)的频度是n(n+1)。同理可得语句(3),(4)和(5)的频度分别是n2,n2(n+1)和n3。 



我们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最坏情况运行时间是 O(n^2),但期望时间是O(nlogn)。通过每次都仔细 地选择基准值,我们有可能把平方情况 (即O(n^2)情况)的概率减小到几乎等于 0。在实际中,精心实现的快速排序一般都能以 (O(nlogn)时间运行。


(六)下面是一些常用的记法

    访问数组中的元素是常数时间操作,或说O(1)操作。一个算法如果能在每个步骤去掉一半数据元素,如二分检索,通常它就取 O(logn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间 。常规的矩阵乘算法是O(n^3),因为算出每个元素都需要将n对元素相乘并加到一起,所有元素的个数是n^2。


指数时间算法通常来源于需要求出所有可能结果。例如,n个元素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的 。指数算法一般说来是太复杂了,除非n的值非常小,因为,在 这个问题中增加一个元素就导致运行时间加倍。不幸的是,确实有许多问题 (如著名的“巡回售货员问题” ,”汉诺塔问题”),到目前为止找到的算法都是指数的。如果我们真的遇到这种情况, 通常应该用寻找近似最佳结果的算法替代之。

(七) 一个经验规则 

有如下复杂度关系 

                  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就会令这个算法不能动了,居于中间的几个则差强人意. 常见的时间复杂度按数量级递增排列依次为:常数0(1)、对数阶0(log2n)、线形阶0(n)、线形对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、…、k次方阶0(nk)、指数阶0(2n)。显然,时间复杂度为指数阶0(2n)的算法效率极低,当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子图像了;


例7:设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))


y++;


解答:T(n)=n1/2 ,T(n)=O(n1/2),最坏的情况是y=0,那么循环的次数是n1/2次,这是一个按平方根阶递增的函数。


(3) x=91; y=100;


while(y>0)


if(x>100)


{x=x-10;y--;}


else x++;


解答: T(n)=O(1),这个程序看起来有点吓人,总共循环运行了1000次,但是我们看到n没有? 没。这段程序的运行是和n无关的,就算它再循环一万年,我们也不管他,只是一个常数阶的函数。如果算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。


(八)算法的时间复杂度不仅仅依赖于问题的规模,还与输入实例的初始状态有关。

例8:在数值A[0..n-1]中查找给定值K的算法大致如下:

   (1) i=n-1;

   (2) while(i>=0&&(A[i]!=k))

   (3)     i--;

   (4) return i; 

    此算法中的语句(3)的频度不仅与问题规模n有关,还与输入实例中A的各元素取值及K的取值有关:

①若A中没有与K相等的元素,则语句(3)的频度f(n)=n;

②若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。



(九)一个示例

(1) int num1, num2;

(2) for(int i=0; i<n; i++){ 

(3)     num1 += 1;

(4)     for(int j=1; j<=n; j*=2){ 

(5)         num2 += num1;

(6)     }

(7) } 


分析:

1.

语句int num1, num2;的频度为1;

语句i=0;的频度为1;

语句i<n; i++; num1+=1; j=1; 的频度为n;

语句j<=n; j*=2; num2+=num1;的频度为n*log2n;

T(n) = 2 + 4n + 3n*log2n


2.

忽略掉T(n)中的常量、低次幂和最高次幂的系数

f(n) = n*log2n


3.

lim(T(n)/f(n)) = (2+4n+3n*log2n) / (n*log2n)

                     = 2*(1/n)*(1/log2n) + 4*(1/log2n) + 3


当n趋向于无穷大,1/n趋向于0,1/log2n趋向于0

所以极限等于3。


T(n) = O(n*log2n)

  评论这张
 
阅读(1602)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2016