数据结构_复杂度讲解(附带例题详解)-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构_复杂度讲解(附带例题详解)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

什么是数据结构？

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

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

什么是算法？

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

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

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

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）。