【数据结构】初识数据结构，十分钟带你玩转算法复杂度

目录

前言：

一、初识数据结构：

1.数据结构：

2.算法：

二、算法效率：

三、算法复杂度：

1.时间复杂度：

①.时间复杂度的概念：

②.大 O 的渐进表示法：

③.最好、最坏与平均：

2.空间复杂度：

3.常见复杂度对比：

总结：

️博客主页：✈️銮同学的干货分享基地

️欢迎关注：点赞收藏✍️留言

️系列专栏：数据结构

【进阶】C语言学习

C语言学习

️代码仓库：数据结构仓库

VS2022_C语言仓库

家人们更新不易，你们的点赞和⭐关注⭐真的对我真重要，各位路过的友友麻烦多多点赞关注，欢迎你们的私信提问，感谢你们的转发！

关注我，关注我，关注我，你们将会看到更多的优质内容！！

---

本文重点 ：

初识数据结构 算法效率 算法复杂度

前言：

嗨喽呀各位小伙伴们，好久不见呀！不知道在过去的一周里，大家有没有认真的进行代码练习呢？

在过去的两个半月中，我们一起系统完整的学习了 C 语言的相关知识，并在进阶板块更进一部地加深了对 C 语言的认知与理解，较为熟练的掌握了 C 语言中的各种代码语法和结构使用，能够用代码来解决相当一些简单的实际问题。

但是仅仅只是学会了语法是远远不够的。从今天起，我们将开始数据结构的学习，让我们的程序从无论是内存角度还是运行角度，都更加优秀，更加结构化，大幅度提升我们程序代码的可读性与可移植性，提升我们的代码书写能力。

一、初识数据结构：

1.数据结构：

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

2.算法：

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

算法具有以下五个特征：

★有穷性(Finiteness)：指算法必须能在执行有限个步骤之后终止。

★确切性(Definiteness)：算法的每一个步骤必须有确切的定义。

★输入项(Input)：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件。

★输出项(Output)：一个算法有一个或多个输出，以反映对输入数据加工后的结果。

★可行性(Effectiveness)：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成。

同时算法还有两个要素：

★数据对象的运算和操作

★算法的控制结构

算法的常见思想有九种：

★ 递推法

★ 递归法

★ 穷举法

★贪心算法

★分治法

★动态规划法

★ 迭代法

★ 分支界限法

★ 回溯法

二、算法效率：

算法的效率一般可以分为时间效率与空间效率。

时间效率指算法执行的时间，依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而空间效率则指的是程序运行所需要占用的空间，依据依据该算法编制的程序在计算机上运行时所占用的全部空间来度量。

再通俗一点的讲，讨论算法的效率，其实就是在研究算法的好坏。而我们在衡量算法的好坏时，通常从时间与空间两个维度出发进行衡量。从时间维度出发研究算法的时间复杂度，从空间维度出发研究算法的空间复杂度。

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算 机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计 算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度，并且在研究算法效率时，基本只研究算法执行的时间效率。

三、算法复杂度：

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。算法的评价主要从时间复杂度和空间复杂度来考虑。

1.时间复杂度：

①.时间复杂度的概念：

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说是无法测算的，只有把我们的程序放在机器上运行起来才能知道。但是我们如果将每个算法都上机进行测试吗将会非常麻烦。因此才产生了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，即为该算法的时间复杂度。

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

例如：

void Func1(int N){int count = 0;for (int i = 0; i < N ; ++ i){for (int j = 0; j < N ; ++ j){++count;}}for (int k = 0; k < 2 * N ; ++ k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);}

在上面这段代码中，第一部分的嵌套循环共执行 N^2 次，第二部分的循环共执行 N*2 次，第三部分的循环共执行 10 次，因此这段代码的时间复杂度 F(N) 为：

F(N) = N^2 + N*2 + 10

即算法的时间复杂度为函数 F(N)。

②.大 O 的渐进表示法：

可是我们发现，在上面的算出的算法时间复杂度中，当我们进行取值：

• N = 10 F(N) = 130
• N = 1000 F(N) = 1002010
• N = 100000 F(N) = 10000200010

我们发现，随着 N 的指数型增长，时间复杂度与 N*2 + 10 的关系越来越小，时间复杂度渐渐取决于最高次幂 N^2。

实际上我们在计算时间复杂度时，并不一定要计算精确的执行次数，而只需要大概执行次数即可。于是这里我们通常使用大 O 的渐进表示法来表示算法的时间复杂度。

★ 推导大O阶方法 ★

1、用常数 1 取代运行时间中的所有加法常数(即表达式为常数，大 O 阶表示为 1)。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是 1，则去除与这个项目相乘的常数。结果即为大 O 阶。

例如上面的时间复杂度使用大 O 的渐进表示法表示即为 O(N^2)。即通过使用大 O 的渐进表示法来进行表示，去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。

③.最好、最坏与平均：

同时一些算法的时间复杂度，还存在着最好、最坏与平均的情况：

最好情况：任意输入规模的最小运行次数(下界)。

最坏情况：任意输入规模的最大运行次数(上界)。

平均情况：任意输入规模的期望运行次数。

例如在长度为 N 的数组中查找数据 X：

最好情况： 1 次找到。

最坏情况： N 次找到。

平均情况：N/2 次找到。

而我们在实际中一般情况下关注的是算法的最坏运行情况。

2.空间复杂度：

空间复杂度的定义：空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少 bytes 的空间，因为 bytes 这个概念对于如今高速发展迅速扩容的计算机内存来说没有太大意义。所以空间复杂度计算的是变量的个数。

空间复杂度计算规则：基本与时间复杂度类似，也使用大 O 渐进表示法。

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

例如：

void BubbleSort(int* a, int n){assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i  a[i]){Swap(&a[i-1], &a[i]);exchange = 1;}}if (exchange == 0){break;}}}

在这段冒泡排序的代码中，除去原本就存在的量的空间外，额外定义的变量有 end 、i 和exchange，共三个，则其空间复杂度的表达式为F(N) =3 ，其表达式为常数，大O 阶表示为O(1)。

3.常见复杂度对比：

在这里我也为各位小伙伴们整理出了一些平日里常见算法对应的空间复杂度：

通过整理出的表格我们可以更加直观的看出，例如立方、平方与线性这样，有高阶存在的算法，空间与时间复杂度取决于高阶算法的复杂度表达式。

将各大 O 阶表示的复杂度绘制成图，能够更加直观的观察各阶类型对复杂度的影响程度：

总结：

到这里我们今天就对数据结构有了一个大致的了解，同时学会了计算算法的时间与空间复杂度，通过算法复杂度的研究，我们可以更加精确的优化我们的代码，提升算法的执行效率，提升我们程序的执行效率，帮助我们写出更加优秀的代码，为我们取得 offer 、走进大厂争取更多的机会。希望各位小伙伴们下去以后可以多多查阅资料，适当寻找相关题型进行巩固训练，切实掌握知识，提升个人代码书写和优化能力。

如果惧怕前方跌宕的山岩，那么生命就永远只能是死水一潭

更新不易，辛苦各位小伙伴们动动小手，三连走一走 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！