【数据结构与算法】--3.复杂度分析

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【数据结构与算法】--3.复杂度分析，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5023字，纯文字阅读大概需要8分钟。

内容图文

一、为什么需要复杂度分析？

代码跑一遍做统计监控的数据虽然很准确，但是属于事后统计分析，局限性在于：

1. 依赖测试环境（硬件）
2. 受测试数据规模的影响很大
   

二、什么是复杂度分析

1. 数据结构和算法是解决“如何让计算机执行时间更快，更生空间”的解决问题。
2. 所以要从执行时间和占用空间两个维度来评估算法的性能。
3. 于是用了时间复杂度和空间复杂度两个概念来描述性能问题，统称为复杂度；
4. 复杂度描述的是算法执行时间（占用空间）与数据规模增长的关系；
   

三、复杂度分析的过程：

时间复杂度

来看看三种分析技巧

1. 大O时间复杂度的由来及表示方法：

所有代码的执行时间与每行代码的执行次数成正比。
所以T(n)=O(f(n));
T(n)表示代码执行的时间；n表示数据规模的大小；f(n)表示代码的执行时间T(n)与f(n)表达式成正比；

2. 时间复杂度分析

1）只关注循环执行次数最多的一段代码
为什么这么说呢，大O复杂度只表示一种变化的趋势，我们通常会忽略掉公式中的常量、低阶、系数只记录一个最大阶的量级。所以在分析一个算法的时候，我们只需要关注执行次数最多的那段代码就可以了，这段核心代码执行次数的n的量级也就是这段代码的时间复杂度。

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

2,3行代码都是常量级的执行时间，与n的大小无关，所以对于复杂度并无影响。循环执行次数最多的是4,5行，所以这块是核心代码，这两行代码被执行了n次,所以时间复杂度为O(n);

2)总复杂度等于量级最大的那段代码的复杂度
这个代码分为三部分， 分别是求 sum_1、 sum_2、 sum_3。 我们可以分别分析每一部分的时间复杂度， 然后把它们放到一块儿， 再取一个量级最大的作为整段代码的复杂度
第一部求sum_1:
这段代码循环执行了100次，所以是一个常量的执行时间，与n的规模无关。这里需要说明的是不管这段代码执行了10000次或10000000次，只要是一个已知的数，与n无关，最终也是一个常量级的执行时间。回到时间复杂度的概念来说，它表示的是一个算法执行效率与数据规模增长的变化趋势，所以不管常量的执行时间多长，我们都可以忽略，因为它本身对增长趋势并无影响。
第二部分求sum_2:
O(n);
第三部分求sum_3:
O(n²);
二三部分看循环次数便可以分析处理，不做赘述。
那么整段代码的复杂度是多少呢，这里需要综合一二三部分取出其中最大的量级。所以，整段代码的时间复杂度为O(n²);

int cal(int n) {

int sum_1 = 0;
int p = 1;  
for (; p < 100; ++p) {
	sum_1 = sum_1 + p;
} 

int sum_2 = 0;
int q = 1;
for (; q < n; ++q) {
	sum_2 = sum_2 + q;
} 

int sum_3 = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
		j = 1;
		for (; j <= n; ++j) {
			sum_3 = sum_3 + i * j;
		}
} 
  return sum_1 + sum_2 + sum_3;
}

** 3)乘法法则–嵌套代码的复杂度等于嵌套内外代码复杂度的乘积**

int cal(int n) {

int ret = 0;
int i = 1;
 	 for (; i < n; ++i) {
   ret = ret + f(i);
   }
 }

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

单独看cal()函数，若f（）只是普通的操作，那么第4-6行的时间复杂度就是，T1(n)=O(n)，但f()在这里并不是一个简单的操作，它的时间复杂度是T2(n)=O(n);
所以，整个cal()函数的时间复杂度为：T(n)=T1(n) * T2(n)=O(n * n)=O(n²);

3.几种常见时间复杂度实例

1) O(1)
只要代码的执行时间不随 n 的增大而增长， 这样代码的时间复杂度我们都记作O(1)。 或者说， 一般情况下， 只要算法中不存在循环语句、 递归语句， 即使有成千上万行的代码，
其时间复杂度也是Ο(1)。

 int i = 8;
 int j = 6;
 int sum = i + j;

2) O(logn)、 O(nlogn)

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

上面这段代码的核心代码是在于第三行，我们只要计算出这段代码会执行多少次就知道了整段代码的时间复杂度
变量 i 的值从 1 开始取， 每循环一次就乘以 2。 当大于 n 时， 循环结束。 还记得我们高中学过的等比数列吗？ 实际上， 变量 i 的取值就是一个等比数列。 如果我把它一个一个列出来， 就应该是这个样子的:
2⁰ 2¹ 2³ 2⁴ …… 2^k…… 2ⁿ =n
x=log2ⁿ 所以，这段代码的时间复杂度为O(log2ⁿ);
如果我们将第三行改为i=i * 3，那么时间复杂度为多少呢？
同上面的计算一样我们可以推论出O(log3ⁿ);
因为对数之间是可以互相转换的，所以log3n=log3² * log2ⁿ
所以O(log3n)=O(log3² * log2ⁿ), 因为log3²是一个常量，
所以O(log3n)=O(log2n)，所以在对数阶的时间复杂度的表示方法里，我们可以忽略对数的底，统一表示为O(logn)；
理解了O(logn)之后就很容易理解O(nlogn)了，结合上面第三个技巧中的乘法法则可以理解，当循环执行n遍时，时间复杂度*n就变成了O(nlogn)；
归并排序，快排，的时间复杂度都是O(nlogn)；

3) O(m+n)、 O(m*n)

int cal(int m, int n) {
 
  int sum_1 = 0;
  int i = 1;  
  for (; i < m; ++i) {
  sum_1 = sum_1 + i;
  } 
  
  int sum_2 = 0;
	int j = 1;
  for (; j < n; ++j) {
  sum_2 = sum_2 + j;
  } 
  
  return sum_1 + sum_2;
}

上述代码可以看出m和n是两个数据规模，我们无法评估m,n谁的量级更大，所以我们在表示复杂度的时候，不能根据第二条法则省略到其中一个取最大了，所以上面的复杂度为O(m+n);
第三条乘法法则依然有效：T1(m)T2(n) = O(f(m) * f(n))=O(mn);

空间复杂度

空间复杂度比时间复杂度分析要简单的多，表示算法的存储空间与数据规模之间的增长关系；

void print(int n) {
 int i = 0;
 int[] a = new int[n];
   for (i; i <n; ++i) {
	   a[i] = i * i;
   }
   for (i = n-1; i >= 0; --i) {
 	  print out a[i]
   }
}

我们逐行来分析，第2行代码中，申请了一个空间来存i，但是它是常量阶的，与数据规模n没有关系，所以可忽略；
第三行申请了一个大小为n的Int类型的数组，下面的代码没有占用过其他的空间，所以整段代码的复杂度为O(n)。
常见的复杂度有:O(1)、 O(n)、 O(n²)，对数阶的复杂度平时用到的很少。

四、小结：

复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率有数据规模之间的增长关系。复杂度分析为我们提供了很好的理论分析的方向，并且与宿主平台无关，能够让我们对自己的程序有一个大致的认识，另外用O复杂度去标识也让程序复杂度有了更直观，效率上也有更感性的体现。编程时候要具备这种复杂度分析的思维。

内容总结

以上是互联网集市为您收集整理的【数据结构与算法】--3.复杂度分析全部内容，希望文章能够帮你解决【数据结构与算法】--3.复杂度分析所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---