什么是算法的时间复杂度

Posted on | In

时间复杂度定义

  • 在进行算法分析时 ,语旬总的执行次次T(n)是关子问题规模n的函数,进而分析T(n)n的变化情况并确定T（n）的数量级。
  • 一般情况下,随着n的增大,T(n)增长最慢的算法为最优算法
  • 算法的时间复杂度也就算法的度量，记作：T（n）=O(f(n)).它表示随问题规模n的增大，算法执行时间增长率和f(n)的增长率相同，乘坐算法的渐进时间复杂度。其中f(n)是问题规模n的某个函数
  • 这样用大写 O()来体现算法时间复杂度的记法,我们称之为大 0 记法 。
  • 常见的有常数阶O(1），线性阶O（n），对数阶O（logn），平方阶O（n2）

推导大O阶方法

  • 用常熟1取代运行时间中所有的加法常熟
  • 在修改后的次数中只保留最高阶项
  • 如果最高阶项存在且不是1,则去除与这个项相乘的常数。得到的结果就是大O阶。

常数阶

高斯求和：求1+2+3+4+5+6…+n 结果集

1
2
3
4
5
6

public static void main(String[] args) {
    int  sum = 0,n = 100; // 执行一次
    sum = (1 + n) *(n/2); // 执行一次
    System.out.println(sum); //执行一次
}

这个算法的运行次数函数是f(n) =3.根据我们推导大 0 阶的方法,第一步就是
把常数项3改为1在保留最高阶项时发现,它根本没有最高阶项,所以这个算法的O(1).

线性阶

  • 线性阶的循环结构会复杂很多。要确定某个算法的阶次,我们常常需要确定某个 特定语句或某个语句集运行的次数。因此,我们要分析算法的复杂度,关键就是要分 析循环结构的运行情况。
1
2
3
4
5
6

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

 /* 时间复杂度为O(1)的程序步骤序列 */
}

它的循环的时间复杂度为 O(n), 因为循环体中的代码须要执行 n 次。

对数阶

1
2
3
4
5
6

int count = 1; 
while (count < n){
 count = count * 2;
 /* 时间复杂度为O(1)的程序步骤序列 */
}
  • 由于每次count 乘以2之后,就距离n更近了一分 。 也就是说,有多少n个2相乘后大于 ,则会退出循。由 $2^x$=n得到x=log2n。 所以这个循环的时间复杂度为O(logn)。
  • 二分查找算法的时间复杂度就是O(logn)。O(logn)的意思是以log为底数（你如果采用二分法,那么就会以2为底数,三分法就会以3为底数）比如当数据增大256倍时，耗时只增加8倍：
1
2
3
4
5
6
7
8
9
10
O(logn)=O(log256)

2x2=4                  //第1次
2x2x2=8                //第2次
2x2x2x2=16             //第3次
2x2x2x2x2=32           //第4次
2x2x2x2x2x2=64         //第5次
2x2x2x2x2x2x2=128      //第6次
2x2x2x2x2x2x2=256(n)   //第7次 7个2相乘后=n
2x2x2x2x2x2x2x2>n      //第8次 个2相乘后大于n

O(nlogn)同理，就是n乘以logn，当数据增大256倍时，耗时增大256*8=2048倍。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。

输入图片说明

觉得本文不错的话，分享一下给小伙伴吧~