一文说懂算法时间空间复杂度分析

2,704 阅读6分钟

什么是数据结构,又什么是算法

百度百科释义:算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制...一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

懂了没?其实我也懵逼。这些定义都很抽象,对理解这两个概念并没有实质性的帮助,你要是深究反而容易陷进误区

表达从简单开始~

形象地说,数据结构就是指存储数据的结构。算法就是操作数据的方法。

图书馆你总去过吧,图书馆员为了方便读者查找书籍,会把书本分门别类的放好并按规律编号。这里排放规律的书籍其实就是一种数据结构

那你怎么来找书呢?是一本一本的找;根据 人文与社科,电子与信息技术,城市规划与建设 书馆寻找;还是到电脑搜索书名再拿着得到的编号找... 这就是 查找的算法

数据结构和算法又为什么常常要一起讲

那是因为算法只能作用于特定的数据结构,而数据结构又会根据自身特点推演出特定的算法

比如刚才的例子:

  • 按规律编号的书籍,可以一本一本找;分书馆找;按索引找;
  • 乱堆连放的书籍,你就只能一本一本找了

数据结构是只是种堆放数据的方式,数据结构与算法研究的是如何快和省的问题,你不根据数据结构的规律特点谈算法是没用的。

时间/空间复杂度分析又是什么

刚才我们说到:数据结构与算法研究的是如何快和省地解决问题 —— 那如何才算快,怎样才是省呢。
所以如何衡量算法的 执行效率,使用空间 是个很重要的标准 —— 这就需要我们的 时间复杂度分析空间复杂度分析
它有多重要呢 —— 我感觉这就是数据结构与算法课程里的半壁江山,之后说的具体结构和算法都是围着这个标准转的

为什么需要时间/空间复杂度分析

算法效率的度量方法内有一种就叫事后统计方法,说白了就是:写个单元测试跑一遍算法,就消耗多少内存,多少时间。

很简单直接。可问题是这个单元测试

  • 在Intel Core i9、Intel Core i3 处理器上跑出的性能不一样
  • 数据量大、数据量小跑出来的性能也不一样

这不就是摆明挖坑给自己,就看什么时候跳嘛。

所以我们需要一个不依赖具体测试环境、具体数据,就可以粗略估计算法执行效率的方法。

那具体是个怎样的方法呢

大 O 复杂度表示法

可有可无的解释:大 O 时间复杂度表示法表示代码执行时间随数据规模增长的变化趋势,也叫渐进时间复杂度,简称时间复杂度。

我们从一段普通的java代码说起~

1   int i;
2   for( i=0; i < n; i++ ){
3       sum = sum + i;
4   }

执行情况:

  • 第 1 行,执行了一遍;
  • 第 2、3 行,执行了n遍;

所以这段普通的java代码执行次数是:2n+1

我们假设每行语句的执行一遍的时间是一个单位时间(unit_time)。所以整段代码总的执行时间:

T(n) = (2n+1)*unit_time

尽管我们不知道 unit_time 的具体值,但是通过公式,我们知道所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

因此我们可以引出这么条公式:T(n) = O(f(n)) (不用记,继续往下看),于是普通的java代码执行时间会演变成:

T(n) = O(2n+1)

然后时间复杂度分析只关注执行次数最多的那段代码,且忽略系数、常量、对数的“底”。于是最后普通的java代码的时间复杂度是:O(n)

时间复杂度分析,说到这里基本概念就说完。撒花~~ 不过还有两个容易产生误会的点,需要三申五令:

1. 只关注执行次数最多的那段代码

1   int i, j, q, n = 100;
2   for ( q=0; q < n; q++ ) { 
3       printf(“I love u\n”);
4   } 
5   
6   for( i=0; i < n; i++ ){
7       printf(“I love u”); 
8       for( j=0; j < n; j++ ){
9           printf(“ three thousand times\n”);
10      }
11  }

执行情况:

  • 第 1 行,执行了一遍;
  • 第 2、3 行,执行了n遍;
  • 第 6、7 行,执行了n遍;
  • 第 8、9 行,执行了nn遍; 所以这段代码执行次数是:1+n+n+(nn),因为:

时间复杂度分析只关注执行次数最多的那段代码,且忽略系数、常量、对数的“底”

所以最后的时间复杂度为:O(n2) ...(n的2次方)

2. 关注代码执行次数

时间复杂度分析,我们本质分析的是什么?—— 时间吗?不,我们看的是代码执行次数。

假设每行语句的执行一遍的时间是一个单位时间(unit_time)—— 是因为有了这个假设,我们才把次数换单位时间,从而推导出O(n)

为什么专门提这一点呢?我们举个例子:

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

如果你说是O(n),恭喜,我赏你一丈红。答错了!认真看我推导... 我们假设 x 为执行次数,那么上面代码 x 和 n 的关系为:

所以执行次数与 n 的关系为:

由于 一次执行次数等于一个单位时间,且对数的“底”。所以最后的时间复杂度为

空间复杂度分析

空间复杂度分析和时间复杂度分析类似,你只需要把 一次执行次数等于一个单位内存大 O 复杂度表示法重推一遍就会啦~

结语

复杂度分析并不难,关键在于多练。从低阶到高阶有:O(1)、O(logn)、O(n)、O(nlogn)、O(n2)。

虽然 复杂度分析还有最好、最坏、均摊(平均)复杂度分析。 但个人感觉 你掌握上面的复杂度分析,再加个均摊复杂度分析。学习工作就够用了。

而均摊复杂度分析,我的理解是

多少种情况 被 各情况的“时间复杂度之和”相除

欢迎点赞+关注,我们下次再聊