算法的时间复杂度计算

发表于   |   分类于   |     |  

[TOC]
时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数)

步骤

1.找出算法中执行次数最多的那条语句，通常是内层循环体
2.计算基本语句的执行次数的数量级，可以忽略所有低次幂和最高次幂的系数
3.用大Ο记号表示算法的时间性能
4.如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加

规则

1.嵌套循环：循环次数相乘
2.并列循环：循环次数相加，其实就是循环次数最大的那个
3.大O表示法中相加项取最高次幂那项：O(N+N^2)=O(n^2)
4.O(1)表示基本语句执行次数是一个常数，算法中不存在循环语句
5.大O只考虑阶数，系数和常数去掉：O(1+n(n+1)/2)=O(n^2)
6.时间复杂度分析的基本策略是：从内向外分析，从最深层开始分析。如果遇到函数调用，要深入函数进行分析。

例子

1.for

1
2
3
int i,j;
  for(i=0;i<n;i++)
    for(j=i;j<n;j++);

执行次数是n+(n-1)+(n-2)+…+1，所以复杂度是O(n^2)

2.log(n)

1
2
3
int i=1;
while(i<n)
    i*=2;

每次执行i都乘以2，设执行次数是x，那么此时的i=1*2*2*2*...*2=2^x，跳出循环应该 2^x>=n，所以执行次数x=log(n)，循环复杂度为O(log(n))

热评文章