数据结构_复杂度讲解(附带例题详解)

---

前言

什么是数据结构？

数据结构是计算机科学中研究数据组织、存储、管理和操作的方法和原则。它涉及到各种不同的数据类型和数据组织方式，包括数组、链表、树、图等。数据结构的设计和实现可以影响到程序的效率和可靠性，因此是计算机科学中非常重要的一个领域。

• （数据结构是计算机存储、组织数据的方式，指相互之间在一种或多种特定关系的数据元素的集合）
• （数据结构就是在内存当中管理数据（管理的核心就是增、删、查、改），在内存中管理数据有很多种方式，比如说链型结构…不同结构有他们各式各样的优越势）

什么是算法？

• 算法就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果
• （算法是对这些数据进行一些处理，就是排序、查找、这些。然后达到我们想要的目的）

---

一. 算法的时间复杂度和空间复杂度

写完一个算法后呢，要评估一下，这个算法效率上跑的怎么样，一个算法衡量它最重要的标准就是它的性能如何，所以数据结构里面给出了评估它一个性能的标准，叫做： 复杂度的计算。 分下来叫：时间复杂度 和 空间复杂度。

1.1 算法效率

算法效率是衡量算法运行时间和所需资源的指标。它可以用时间复杂度和空间复杂度来表示。算法效率越高，运行速度越快，所需资源越少。

1.2 如何衡量一个算法好坏

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。 因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的 即时间复杂度和空间复杂度。

二. 时间复杂度

2.1 时间复杂度概念

在计算机科学中，算法的时间复杂度是一个函数 ，它定量描述了该算法的运行时间。时间复杂度是衡量算法时间效率的指标。它表示算法运行时间与输入规模的增长关系。常见的时间复杂度有 O(1)、O(log n)、O(n)、O(n log n)、O(n²) 等。时间复杂度越低，算法效率越高。

即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。

例题一

例题一分析

第一个for循环里嵌套了一个for循环，总的循环会执行NN次；
第二个for循环会执行2N次；
while循环固定 – 10 次 ；

所以Func1 执行的基本操作次数是：N^2+2*N+10

但是，我们需要注意的是，实际我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而是只需要大概执行次数，抓大头，那么这里我们使用大O的渐进表示法。

例如：N^2+2*N+10
当 N = 10 F(N) = 130 ;
N = 100F(N) = 10210 ;
N = 1000F(N) = 1002010 ;

随着N越来越大，2N+10的值与N^2的值相比 2N+10的值太小，可以忽略，那么这里用大O渐进表示法 时间复杂度记为 O（N^2）。

实例一

实例一分析

Func2准确的时间复杂度是: 2N+10:这个 +10 对结果影响不大，可以忽略，省略掉。
那最后是O (2N) 还是O (N) 呢。
为什么最后取得是O (N)。

1. 在这个表达式里面一般会去阶数最高的一个项，因为这个项是对表达式影响最大的。
2. 其次还会忽略掉它的系数

三. 空间复杂度

是对一个算法在运行过程中额外临时占用存储空间大小的量度。
空间复杂度不是程序占用了多少 bytes 的空间，所以空间复杂度算的是变量的个数
空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法

注意：
函数运行时所需要的栈空间（存储函数、局部变量、一些寄存器信息等）在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显示申请的额外空间来确定。

实例

实例问题解析

1. 问题一：不算，因为它不是为了解决这个排序额外开的空间，因为这个数组存的是本来提供的数据样本。
2. 问题二：是为了解觉这个排序，额外开的空间。
3. 问题三：这三个变量是因为我们在排序的过程中我们要进行 循环、迭代 … 定义的变量。三个 — 常数个 — 空间复杂度 – O(1) --不是一个，是常数个。

四. 常见复杂度对比

五. 常见时间复杂度以及复杂度oj练习