数据结构：算法复杂度

前言

数据结构（Data Structure）是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有用途都有用，所以我们要学各式各样的数据结构，如：线性表、树、图、哈希等

算法（Algorithm)：就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。

一.算法效率

一个算法的好坏不能用它的算法的执行时间。

例子：

在这里插入图片描述

这段代码，我们可知每次执行打印出来的时间结果是不一样的。

我们来看一道轮转数组的题

在这里插入图片描述

我们来看第一种解法
在这里插入图片描述

点击运行，发现测试用例都通过了。

但是当我们提交之后，发出了报错：超出时间限制。当数组数据太多的时候，该代码通过不了，这说明我们这个算法不是很好。

在这里插入图片描述

从上面例子我们知道一个算法能写出来，不代表该算法就是好的，我们需要一个指标来衡量算法的好坏，接下来我们来引进复杂度的概念，通过复杂度来判断一个算法的好坏。

二.复杂度的概念

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

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

1.时间复杂度

定义：在计算机科学中，算法的时间复杂度是一个函数式T(N)，它定量描述了该算法的运行时间。时间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运行时间呢？

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

2．同一个算法程序，用一个老低配置机器和新高配置机器，运行时间也不同。

3．并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。

那么算法的时间复杂度是一个函数式T(N）到底是什么呢？这个T(N）函数式计算了程序的执行次数。通过c语言编译链接章节学习，我们知道算法程序被编译后生成二进制指令，程序运行，就是cpu执行这些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执行次数的函数式T(N)，假设每句指令执行时间基本一样（实际中有差别，但是微乎其微），那么执行次数和运行时间就是等比正相关，这样也脱离了具体的编译运行环境。执行次数就可以代表程序时间效率的优劣。比如解决一个问题的算法a程序T(N)=N，算法b程序T(N)=N^2，那么算法a的效率一定优于算法b。

影响时间复杂度的条件有：每条语句的执行时间*每条语句的执行次数。由于每条语句的执行时间无法给出准确数据，所以每条语句的执行时间即使有差别但是微乎其微，可以忽略不计，认为每条语句的执行时间是相同的。

我们来看例题：

在这里插入图片描述

实际中我们计算时间复杂度时，计算的也不是程序的精确的执行次数，精确执行次数计算起来还是很麻烦的（不同的一句程序代码，编译出的指令条数都是不一样的），计算出精确的执行次数意义也不大，因为我们计算时间复杂度只是想比较算法程序的增长量级，也就是当N不断变大时T(N）的差别，上面我们已经看到了当N不断变大时常数和低阶项对结果的影响很小，所以我们只需要计算程序能代表增长量级的大概执行次数，复杂度的表示通常使用大O的渐进表示法。

我们要知道：时间复杂度只能用来表示输入条件对时间的影响趋势。

虽然我们写出了T(n)，但是算法的复杂度用大O的渐进表示法来表示。

2.大0的渐进表示法

大O符号（Big O notation)：是用于描述函数渐进行为的数学符号

推导大O阶规则

1.时间复杂度函数式T(N）中，只保留最高阶项，去掉那些低阶项，因为当N不断变大时，低阶项对结果影响越来越小，当N无穷大时，就可以忽略不计了。

2.如果最高阶项存在且不是1，则去除这个项目的常数系数，因为当N不断变大，这个系数对结果影响越来越小，当N无穷大时，就可以忽略不计了。

3.T(N）中如果没有N相关的项目，只有常数项，用常数1取代所有加法常数。

所以我们上面所举的例子，该函数的时间复杂度为：O(n^2)。

还要记住的一点是：大O的渐进表示法在实际中一般情况关注的是算法的上界，也就是最坏运行情况。