C语言数据结构之算法复杂度

目录

一、数据结构是什么

二、算法是什么

三、算法的效率

        3.1 复杂度的概念

四、时间复杂度

        4.1 大O渐进表示法

        4.2 算法题分析

五、空间复杂度

        5.1 复杂度对比

        5.2 算法题题分析

---

正文开始

一、数据结构是什么

每个计算机专业的同学在大学都会接触到一门计算机必修课《数据结构与算法》

在大数据时代，我们要将数据存储、组织起来必须得依靠数据结构，指相互之间存在一种或多种特定关系的数据元素的集合。没有一种数据结构对所有用途都有用，所以我们要学各式各样的数据结构。

二、算法是什么

算法：就是定义良好的计算过程。

比如说：将一个数组升序排序并输出，可以将数组每个元素比较一下看谁小放前面，也可以用冒泡排序对数组进行排序，或者快速排序等等多种解法，你要找到最优的解法，就称为最优算法。

对标大厂的岗位：算法工程师。

三、算法的效率

有那么多种算法，如何衡量一个算法的好坏呢？

通过复杂度衡量

3.1 复杂度的概念

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

时间复杂度主要衡量算法的运行快慢（程序给出结果要多久），而空间复杂度主要衡量一个算法运行所需要的额外空间。经过计算机行业的迅速发展，计算机的内存容量已经达到了很高的程度，所以我们已经不再特别关注一个算法的空间复杂度。

四、时间复杂度

在数学的学习中，求解未知数有一元一次方程ax + b = 0 、二元一次方程ax+by+c=0.....

在计算机科学中，计算算法的时间复杂度用函数式T(N)来表示。时间复杂度用来衡量程序的运行时间效率，接下来我用C语言中clock计算一下某个程序的运行时间：

以上计算的是两个for循环所需要的时间，t1记录开始时间，t2记录结束时间，两个一减就是for循环所需时间

计算出来的时间是13099毫秒，那么13099毫秒就一定是它真实执行时间吗？在运行几次看看

可以发现：程序每次运行的时间都不一样，无法精确给出一个时间，只能给出一个差不多的数字，所以我们无法通过clock函数计算出程序执行的时间复杂度

（1）因为程序运行时间和编译环境和运行机器的配置都有关，比如同一个算法程序，用一个老编译器进行编译和新编译器在同样机器下运行时间不同

（2）同一个算法程序用一个低配置机器和新高配置机器，运行时间不同

（3）并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估（程序写完才能用clock函数计算）

那么算法的时间复杂度是一个函数式T(N)到底是什么呢？

这个函数式计算了程序的执行次数，是写程序前通过理论思想计算评估的一个函数式，用来表示输入条件N对时间的影响趋势。

上面我已经通过clock给大家演示过无法精确计算出程序的时间，那么影响时间复杂度的条件有：每条语句的执行时间*每条语句的执行次数。由于无法给出精确时间数据，所以每条语句的执行时间即使有差别但是微乎其微，我们可以忽略不计，认为每条语句的执行时间是相同的（上面例子13009毫秒和13144毫秒差别不大忽略不计之间差别）

既然每条语句的执行时间忽略不计，那么影响时间复杂度的条件为：每条语句的执行次数

例如以上代码：count=0语句只执行了一次，++count语句在两个for循环内部，第一个for循环循环N次，第二个for循环也循环N次，所以++count语句执行了n^2次。用时间复杂度函数式T(N) = n^2,其中N表示影响时间复杂度的输入条件，N给的值不同，循环的次数不同算法的时间复杂度T(N)也就不同

有同学可能会问：程序时间复杂度除了++count外不是还有个count = 0语句的执行次数吗？怎么不加上为：T(N) = n^2 + 1

实际中我们计算时间复杂度时，计算的也不是程序的精准执行次数，计算出精准次数意义不大，因为我们计算时间复杂度只是想比较算法程序的增长量级，也就是输入条件N不断变大时T(N)的差别。T(N) = n^2+1随着N的增大，加1对整个程序时间复杂度影响不大（它都已经n^2了+-1已经影响不大）所以忽略不计，我们只需要计算程序能代表增长量级的大概执行次数，既然是大概的，我们通常用大O的渐进表示法。

4.1 大O渐进表示法

用于描述函数渐进行为的数学符号，表示算法的复杂度

4.2 算法题分析

案例一：

   

T(N)用来表示输入条件N对时间的影响趋势。

for循环中++count的执行次数为2N，而while内部++count的循环次数为10

T(N) = 2N+10 根据大O阶规则（1）：2N>10，10去掉；规则（2）：常量系数2去掉

案例二：

++count执行多少次受 k<100 影响所以T(N)=100，根据大O规则（3）：写成O(1)

其中1不是表示程序只执行一次，而是用1取代常量

案例三：

五、空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中因为算法的需要额外临时开辟的空间。也使用大O渐进表示法，规则与其一样。

注意：函数运行时所需的栈空间（存储参数、局部变量、一些寄存器信息等）在编译期间已经确定好了，空间复杂度计算的是函数运行时所需的额外空间。

案例一：

BubbleSort的函数栈帧在编译期间就已经分配好了，其空间复杂度是计算函数内所额外申请的空间，有exchange等有限个局部变量，根据大O表示法的规则，使⽤常数个额外空间为：O(1)

案例二：

执行一次Fac函数，内部递归调用一次Fac(N-1)*N，函数递归的复杂度取决于函数调用的次数，Fac函数内部调用了n-1次，当N=0时不再调用，O(n-1)根据大O表示法规则，最后为：O(n)

5.1 复杂度对比

从以上表格可以看出数据n的数值不断增大，不同空间复杂度所占用空间的比较

5.2 算法题分析

此处开辟的是一个二维数组，数组有n行，每行分别有1,2,3,...n列，等差数列计算公式是n(n + 1)/2个元素空间，根据大O规则，空间复杂度为n^2

图解：

---

完