佩奇学编程 | 复杂度分析原来这么简单

1、数据结构是用来干嘛的?

数据结构与算法的诞生是让计算机「执行的更快」、「更省空间」的。

2、用什么来评判数据结构与算法的好坏?

从「执行时间」和「占用空间」两个方面来评判数据结构与算法的好坏。

3、什么是复杂度?

用「时间复杂度」和「空间复杂度」来描述性能问题,两者统称为复杂度。

4、复杂度描述了什么?

复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。

1、和性能分析相比有什么优点?

辅助度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。

2、为什么要复杂度分析?

复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。

1、什么方法可以进行复杂度分析?

方法:「大 O 表示法」

2、什么是大 O 表示法?

算法的「执行时间」与每行代码的「执行次数」成正比【T(n) = O(f(n)) 】=》其中T(n)表示算法执行总时间,f(n)表示每行代码执行总次数,而n往往表示数据的规模。

3、大 O 表示法的特点?

由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势,常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响,所以在做时间复杂度分析时忽略这些项。

4、复杂度分析法则

  • [单段代码看频率]:看代码片段中「循环代码」的时间复杂度。
  • [多段代码看最大]:如果多个 for 循环,看「嵌套循环最多」的那段代码的时间复杂度。
  • [嵌套代码求乘积]:循环、递归代码,将内外嵌套代码求乘积去时间复杂度。
  • [多个规模求加法]: 法有两个参数控制两个循环的次数,那么这时就取二者复杂度相加。

------------------❤------------------

时间复杂度

1、什么是复杂度?

所有代码的「执行时间 T(n)」 与每行代码的「执行次数n」 成正比【T(n) = O(f(n)) 】。

2、分析的三个方法

■ 最多法则

忽略掉公式中的常量、低阶、系数,取最大循环次数就可以了,也就是循环次数最多的那行代码。

Example

1// 求n个数字之和
2int xiaolu(int n) {
3   int sum = 0;
4   for (int i = 1; i <= n; ++i) {
5     sum = sum + i;
6   }
7   return sum;
8 }

分析

-------------------------------------------

第二行是一行代码,也就是常量级别,与 n 没有关系,可以忽略,四、五行代码是我们重点分析对象,与 n 有关,时间复杂度就是反映执行时间和 n 数据规模的关系。求 n 个数据之和需要执行 n 次。所以时间复杂度为 O(n)。

加法法则

总复杂度等于循环次数最多的那段复杂度。

Example

 1int xiaolu(int n) {
 2   int sum = 0;
 3   //循环一
 4   for (int i = 1; i <= 100; j++) {
 5     sum = sum + i;
 6   }
 7   //循环二
 8   for (int j = 1; j <= n; j++) {
 9      sum = sum + i;
10   }
11 }

分析

-------------------------------------------

上边有两个循环,一个循环 100 次,另一个循环 n 次,我们选择循环次数最多的那一个且和「数据规模 n 」相关的循环。由上可知,我们很容易选出循环二,即和数据规模 n 有关,循环次数最多,循环次数最多的那段代码时间复杂度就代表总体的时间复杂度,为 O(n) ;

乘法法则

当我们遇到嵌套的 for 循环的时候,怎么计算时间复杂度呢?那就是内外循环的乘积。

Example

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

分析

-------------------------------------------

外循环一次,内就循环 n 次,那么外循环 n 次,内就循环 n*n 次。所以时间复杂为 O(n²)。

空间复杂度

1、什么是空间复杂度?

表示算法的「存储空间」与「数据规模」之间的增长关系

Example

  int i = 0;
  int[] a = new int[n];
  for (i; i <n; ++i) {
    a[i] = i * i;
  }

分析

-------------------------------------------

在所有代码中,我们很容易寻找到存储空间相关的代码,就是第二行,申请了一个 n 大小的存储空间,所以空间复杂度为 O(n)。

2、最常见的空间复杂度

O(1)、O(n)、O(n²)。

O(1)

常量级的时间复杂度表示方法,无论是一行代码,还是多行,只要是常量级的就用 O(1) 表示。

Example

1int i = 1;
2int j = 2;
3int sum = i + j;

分析

-------------------------------------------

因为这 3 行代码,也就是常量级别的代码不随 n 数据规模的改变而改变。(循环、递归除外)

O(logn) | O(nlogn)

对数阶时间复杂度」,最难分析的一种时间复杂度。

Example

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

分析

-------------------------------------------

要求这段代码的时间复杂度就求这段代码执行了多少次,看下图具体分析。

补充

-------------------------------------------

不管是以 2 为底、以 3 为底,还是以 10 为底,可以把所有对数阶的时间复杂度都记为 O(logn),因为对数之间可以转换的,参照高中课本。

O(m+n) | O(m*n)

参照上边讲到的加法和乘法法则。

1、最好、最坏时间复杂度

所谓的最好、最坏时间复杂度分别对应代码最好的情况和最坏的情况下的执行。

Example

1 //在一个 array 数组中查找一个数据 a 是否存在
2for (int i = 1; i < n; i++) {
3    if (array[i] == a) {
4       return i;
5    }
6 }

分析:

-------------------------------------------

1、最好情况就是数组的第一个就是我们要查找的数据,上边代码之执行一遍就可以,这种情况下的时间复杂度为最好时间复杂度,为 O(1)。

2、最坏的情况就是数组的最后一个才是我们要查找的数据,需要循环遍历 n 遍数组,也就对应最坏的时间复杂度为 O(n) 。

2、平均时间复杂度

平均时间复杂度需要借助概率论的知识去分析,也就是我们概率论中所说的加权平均值,也叫做期望值。

分析

-------------------------------------------

比如上方的例子,假设我们查找的数据在数组中的概率为 1/2;出现在数组中的概率为 n/1,根据下边的公式就可以算出出现的概率为 1/2n 。

然后我们再把每种情况考虑进去,就可以计算出平均时间复杂度。

3、均摊时间复杂度

■什么是均摊时间复杂度?

比如我们每 n 次插入数据的时间复杂度为 O(1),就会有一次插入数据的时间复杂度为 O(n),我们将这一次的时间复杂度平均到 n 次插入数据上,时间复杂度还是 O(1)。

■ 摊还分析

比如我们每 n 次插入数据的时间复杂度为 O(1),就会有一次插入数据的时间复杂度为 O(n),我们将这一次的时间复杂度平均到 n 次插入数据上,时间复杂度还是 O(1)。

■ 适用场景

一般应用于某一数据结构,连续操作时间复杂度比较低,但是个别情况时间复杂度特别高,我们将特别高的这一次进行均摊到较低的操作上。

■ 几种复杂度性能对比

各个时间复杂度的性能

本文分享自微信公众号 - 小詹学Python(xiaoxiaozhantongxue)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏逸繁

利用逻辑回归进行简单的人群分类解决广告推荐问题

  逻辑回归又称对数几率回归是离散选择法模型之一,逻辑回归是一种用于解决监督学习问题的学习算法,进行逻辑回归的目的是使训练数据的标签值与预测出来的值之间的误差最...

8520
来自专栏35岁开始自学编程

整理总结 python 中时间日期类数据处理与类型转换(含 pandas)

我自学 python 编程并付诸实战,迄今三个月。 pandas可能是我最高频使用的库,基于它的易学、实用,我也非常建议朋友们去尝试它。——尤其当你本身不是程序...

7610
来自专栏CU技术社区

故宫下雪之后!我花了45秒,用Python给它画了一组手绘图

不过,恋习Python突然想到,可以通过Python将故宫的建筑物图片,转化为手绘图(素描效果)。效果图如下:

10730
来自专栏Java工程师成长之路

Excel解析工具easyexcel全面探索

之前我们想到Excel解析一般是使用POI,但POI存在一个严重的问题,就是非常消耗内存。所以阿里人员对它进行了重写从而诞生了easyexcel,它解决了过于消...

30330
来自专栏CU技术社区

IoT前沿|纽约出租车数据交给Pravega分析,会怎么样?

在这里,你的全身上下都被数据围绕,无处不在的物联网、穿梭自如的无人驾驶汽车让数据源源不断产生,就像开着的水管,数据源一直流出。你发现曾经用于分析大数据的方法已经...

8020
来自专栏CU技术社区

Linux 系统进程、线程之间的爱恨纠葛...

当一个程序开始执行后,在开始执行到执行完毕退出这段时间内,它在内存中的部分就叫称作一个进程。

6820
来自专栏CU技术社区

编写 Shell 脚本的最佳实践

由于工作需要,最近重新开始拾掇 shell 脚本。虽然绝大部分命令自己平时也经常使用,但是在写成脚本的时候总觉得写的很难看。而且当我在看其他人写的脚本的时候,总...

3210
来自专栏分布式系统进阶

学习mmap

最近在工作中遇到一个mmap使用相关的问题,造成了一定的困惑,于是花了些时间补了下 mmap的功课,在这里分享给大家,错误和不足之处大家多指教。

6940
来自专栏CU技术社区

Shell 的18条常用命令整理

Linux上的文件以.开头的文件被系统视为隐藏文件,仅用ls命令是看不到他们的,而用ls -a除了显示一般文件名外,连隐藏文件也会显示出来。

3410
来自专栏CU技术社区

硬核小哥教你上手 LaTeX+Vim;1700页数学笔记火了!全程敲代码,速度飞快易搜索

不到一天,相关推文就已经有2000多赞,Hacker News论坛上盖了200多楼。

7920

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励