菜鸟笔记
提升您的技术认知

一文搞懂算法的时间复杂度与空间复杂度-ag真人游戏

一 时间复杂度的概念

一般情况下,算法的基本操作重复执行的次数是模块n的某一函数f(n),因此,算法的时间复杂度记做 t(n) = o(f(n))。 随着模块n的增大,算法执行的时间增长率f(n)的增长率成正比,所以f(n)越小,算法的时间复杂度越低,算法的效率越高。
时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数)

举个简单的例子:

int value = 0;                    // 执行了1次
for (int i = 0; i < n; i  ) {     // 执行了n次
    value  = i;
}

这个算法执行了 1 n 次,如果n无限大,我们可以把前边的1忽略,也就是说这个算法执行了n次。时间复杂度常用大o符号表示,这个算法的时间复杂度就是o(n)。

二 计算时间复杂度

  1. 计算出基本操作的执行次数t(n)
    基本操作即算法中的每条语句(以;号作为分割),语句的执行次数也叫做语句的频度。在做算法分析时,一般默认为考虑最坏的情况。
  2. 计算出t(n)的数量级
    求t(n)的数量级,只要将t(n)进行如下一些操作:
    忽略常量、低次幂和最高次幂的系数,令f(n)=t(n)的数量级。
  3. 用大o来表示时间复杂度
    当n趋近于无穷大时,如果lim(t(n)/f(n))的值为不等于0的常数,则称f(n)是t(n)的同数量级函数。记作t(n)=o(f(n))。
    只保留最高阶项,最高阶项存在且不是1,则去除与这个项相乘的常数。

用一个例子来表明以上的步骤:

for(i=1;i<=n;  i)
  {
     for(j=1;j<=n;  j)
     {
         c[ i ][ j ]=0; //该步骤属于基本操作 执行次数:n^2
          for(k=1;k<=n;  k)
               c[ i ][ j ] =a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数:n^3
     }
  } 

第一步计算基本语句执行次数:t(n)= n^2 n^3;
第二步t(n)的同数量级,我们可以确定 n^3为t(n)的同数量级;
第三步用大o表示时间复杂度:t(n)=o(n^3)。

三 常见的时间复杂度

执行次数函数 名称
3 o(1) 常数阶
2n 3 o(n) 线性阶
3n2 2n 1 o(n2) 平方阶
5log2n 2 o(log2n) 对数阶
2n 3nlog2n 1 o(nlogn) nlog2n阶
6n3 2n2 3n 4 o(n3) 立方阶
2n o(2n) 指数阶

最常见的多项式时间算法复杂度关系为:

o(1) < o(logn) < o(n) < o(nlogn) < o(n2) < o(n3)

指数时间算法复杂度关系为:

o(2n) < o(n!)< o(nn)

举个例子来说明上述的时间复杂度:

i=1;       // 执行次数:1
while (i<=n)
   i=i*2;  
   // 频度为f(n),2^f(n)<=n;f(n)<=log2n
   // 每次i*2后,距离结束循环更近了。也就是说有多少个2相乘后大于n。
   // 取最大值f(n)=log2n,t(n)=o(log2n )

四 复杂情况的时间复杂度分析

1.并列循环复杂度分析

for (i=1; i<=n; i  )
  for (j=1; j<=n; j  )
          x  ;     //o(n2)

2.函数调用的复杂度分析

public void printsum(int count){
    int sum = 1;
    for(int i= 0; i

记住,只有可运行的语句才会增加时间复杂度,因此,上面方法里的内容除了循环之外,其余的可运行语句的复杂度都是o(1)。
所以printsum的时间复杂度 = for的o(n) o(1) = 忽略常量 = o(n)

五 空间复杂度

空间复杂度(space complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做s(n)=o(f(n))。
比如直接插入排序的时间复杂度是o(n^2),空间复杂度是o(1) 。而一般的递归算法就要有o(n)的空间复杂度了,因为每次递归都要存储返回信息。
例如关于o(1)的问题, o(1)是说数据规模和临时变量数目无关,并不是说仅仅定义一个临时变量。举例:无论数据规模多大,我都定义100个变量,这就叫做数据规模和临时变量数目无关。就是说空间复杂度是o(1)。

网站地图