初阶数据结构1 算法复杂度

1.数据结构概念

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

2.算法

算法(Algorithm):就是定义良好的计算过程，他取⼀个或⼀组的值为输⼊，并产⽣出⼀个或⼀组值作为
输出。简单来说算法就是⼀系列的计算步骤，⽤来将输⼊数据转化成输出结果。

程序就是算法加数据结构

良好

针对算法良好意味着算法具有一系列优化的性能，‌包括但不限于时间复杂度、‌空间复杂度、‌正确性、‌健壮性等方面的优化。‌这些优化使得算法能够更好地适应不同的应用场景，‌提高处理问题的效率和准确性。‌

2.1复杂度的概念

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

时间复杂度 等于运行次数
因为对于不同环境下的程序运行时间不可估计，但是算法的运行次数是相同的。我们可以通过

int begin=clock();
{
算法
}
int end=clock()
printf("time:%d",end-begin);
1
2
3
4
5
6

求解算法的运行时间

3.时间复杂度

定义：在计算机科学中，算法的时间复杂度是⼀个函数式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的渐进表⽰法。

3.1大O的渐进表示法

1.时间复杂度函数式T(N)中，只保留最⾼阶项，去掉那些低阶项，因为当N不断变⼤时，
低阶项对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。
2. 如果最⾼阶项存在且不是1，则去除这个项⽬的常数系数，因为当N不断变⼤，这个系数
对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。
3. T(N)中如果没有N相关的项⽬，只有常数项，⽤常数1取代所有加法常数。

实例

注意课件中和书籍中 log2 n 、 log n 、 lg n 的表⽰
当n接近⽆穷⼤时，底数的⼤⼩对结果影响不⼤。因此，⼀般情况下不管底数是多少都可以省略不 写，即可以表⽰为 log n
不同书籍的表⽰⽅式不同，以上写法差别不⼤，我们建议使⽤ log n

---

可以自己尝试一下，计算各个函数的T（N）和O（N）

通过上⾯我们会发现，有些算法的时间复杂度存在最好、平均和最坏情况。 最坏情况：任意输⼊规模的最⼤运⾏次数(上界)
平均情况：任意输⼊规模的期望运⾏次数 最好情况：任意输⼊规模的最⼩运⾏次数(下界)
⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界，也就是最坏运⾏情况。

4.空间复杂度

空间复杂度也是⼀个数学表达式，是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。
空间复杂度不是程序占⽤了多少bytes的空间，因为常规情况每个对象⼤⼩差异不会很⼤，所以空间复
杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似，也使⽤⼤O渐进表⽰法。
注意：函数运⾏时所需要的栈空间(存储参数（define定义的常量）、局部变量、⼀些寄存器信息等)在编译期间已经确定好
了，因此空间复杂度主要通过函数在运⾏时候显式申请（往往是针对动态内存开辟或者是函数递归时）的额外空间来确定

5.常见复杂度的比对

算法的优化随着社会的发展要求越来越高，大规模的输入也越来越对。针对小规模的输入算法之间的运行效率几乎没有差距（此时我们可以追求算法的简易性），但是针对大规模的输入我们的算法一定要是良好的