算法分析—基础的复杂度分析

算法:是为了求解一个问题所需要遵循的,被清楚定义的简单指令等集合.
咸鱼:就是一组按照对应规则执行的方法(也就是计算方法)

对于一个问题,一旦某种算法给定并且被确定是正确的,那么最重要的一步就是确定这个算法会消耗多少时间,空间等资源的问题

事后分析法:把代码跑一遍看对应的资源消耗,对算法性能进行估算

但是,事后分析法存在如下局限:
1. 测试结果依赖测试环境(如:i3处理器和E9处理器消耗的时间肯定不同)
2. 结果受数据规模等影响(如:小规模数据插入排序可能会比快速排序还要快)
综上:我们需要一种不局限于具体数据来测试,就能粗略估算出代码执行效率的方法——时间/空间复杂度分析方法.
咸鱼:时间/空间复杂度分析的全称是时间/空间相对增长率复杂度分析.划重点:相对增长率.类比初中物理的加速度

大O复杂度表示法:
时间复杂度,又称"渐进式时间复杂度",表示代码执行时间与数据规模之间的增长关系。官方定义当存在常数a,b .使得N小于等于b时,函数A(N)大于等于 a * 函数B(N),记作:A(N) = O(B(N)).这个 O 就表示时间复杂度.(小写o只大于不等于)
咸鱼:就是将代码算法执行时间抽象为函数A,A在处理x规模等数据时也就是A(x),永远不会大于O(B(x))中的B(X).在简单的说就是算法不管怎么执行消耗等时间也不会超过B(x),所以又叫上界

算法时间复杂度,也就是算法时间的量度,记作:T(n)=O(f(n))。它表示随着问题n的规模的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中f(n)是关于问题规模n的某个函数。我们用O()来表示时间复杂度的写法,简称为大O写法。

我们可以把f(n)理解为算法基本操作执行的次数,算法执行操作的次数越多,需要的时间也会越多。如果能找出f(n)的表达式,那么可以近似推算出T(n)的表达式。我们一般把算法中所涉及循环语句最里层的操作作为基本操作,来计算出该基本操作执行的次数,作为f(n)的值,进而得出时间复杂度。

 int loopAdd(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }

咸鱼:上面的代码直接数代码需要计算次数,如:int sum = 0; int i = 1;都执行一次,for里面执行n次(忽略for里面等i<=n;i++其实忽略也没什么见下).
所以粗略估计代码要执行:2 + n次.
因为我们计算的时增长率,所以当n无限大的时候,这个2次就是卖萌的.类比大学学的函数求极限知识,同理n的系数并不重要(所以我们这里也去掉n的系数).所以上面代码的时间复杂度为O(n)
在此我们只需要关心量级最大的表达式.如O(2 + n + n^2 + n^3),这里n的3次方量级最大,所以可以直接写成O(n^3)

实用方法:

  1. 只关心循环执行次数最多的代码
  2. 总复杂度等于量级最大那段代码的复杂度
  3. 嵌套循环复杂度等于嵌套内外两个循环的复杂度等乘积(如:for(n){for(n)} = n * n = n^2)

常见时间复杂度:
O(1):
顺序结构语句中,一条代表基本操作的语句

 int a = 1;
 int b = 2;
 int sum = a + b;

O(n):
用于线性阶的算法一般会涉及到单循环,如上面的例子

O(logn)、O(nlogn):
拥有对数阶的算法,一般是涉及到连续乘以相同的数值,看要乘多少次才能接近或超过目标值

 i=1;
 while (i <= n)  {
   i = i * 2;
 }

O(m+n)、O(m*n):
m和n的和或乘积,一般时涉及两个影响增长率的常数m和n,且无法确定m和n等数值关系.
平方阶,一般该算法就是涉及到双重循环的操作(两个for嵌套都循环n次)


int loopAdd(int m, int n) {
  int s1 = 0;
  int i = 1;
  for (; i < m; ++i) {
    s1 = s1 + i;
  }

  int s2= 0;
  int j = 1;
  for (; j < n; ++j) {
    s2= s2+ j;
  }

  return s1+ s2;
}

空间复杂度:把时间换成空间而已,计算占用多少内存,而不是时间.

常见复杂函数图.jpg

更新时间:2020-01-20 19:43:48

本文由 寻非 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.zhouning.group/archives/算法分析基本复杂度
最后更新:2020-01-20 19:43:48

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×