【数据结构与算法】第1课—算法复杂度

1. 数据结构

• 数据结构是计算机存储、组织数据的方式，指相互之间存在一种和多种特定关系的数据元素的集合，常见的有线性表、树、图、哈希等

2. 算法

• 算法：就是制定一个良好的计算过程，取一个或一组值作为输入，并产生一个或一组值作为输出
• 简单来讲，算法就是一系列的计算步骤，用来将输入数据转化为输出结果

3. 算法效率

  我们先来看个简单的例子

  这个时候可能就满足不了，那么我们如何去判断一个代码的好坏呢？

4. 算法复杂度

• 衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的
• 时间复杂度主要衡量一个算法运行速度快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间

5. 算法时间复杂度

• 为什么不用程序执行速度的快慢来作为判断一个算法的好坏呢？
• 这是因为相同的程序在不同的计算机、不同的编译器上、乃至同一台计算机上执行速度都有所不同，并且时间只能在程序编写好后才可以进行测试，因此它不会直接用来作为衡量程序好坏的标准

• 计算机科学规定了，作为衡量一个算法好坏的算法时间复杂度是一个表达式T(N),它用来计算程序的执行次数
• 如果一个算法a程序的T(N)=N,另一个算法b程序的T(N)=N^2,那么算法a的效率一定优于算法b

---

5.1 大O的渐进表示法

• 前面我们讲过，T(N)表达式中可能存在对它影响很小的变量和常量，因此我们需要抓大头来表示程序的变化趋势，因此就引入了大O的渐进表示法

• 大O表示规则：
• 时间复杂度表达式T(N)中，只保留高阶项，去掉低阶项，用来表示程序执行次数变化的趋势
• 如果高阶项存在不是1，不将与高阶项相关的常数系数计算在内，因为随着N不断变大，常数系数对结果影响也不大
• T(N)中如果高阶项就是常数，那么直接写成O(1),用1来代替所有的常数，其中1并不表示程序只执行一次，而是表示它与执行算法所需的时间与输入数据的数量或大小无关

---

5.2 时间复杂度示例

---

• 通过上述例子可以看出，大O渐进表示法一般关注的是算法的上界，也就是最坏的运行情况

6. 空间复杂度

• 函数运行时所需要的栈空间（存储参数、局部变量、一些寄存器信息等）在编译器期间已经确定好了，因此空间复杂度主要考虑函数在运行时额外申请的空间
• 空间复杂度也用大O表示法

---

---

6.1 练习1

---

6.2 练习2

• 创建新的数组，将k个数据放入新的数组中，再将剩下的数据放进去
• 空间复杂度O(N)

---

6.3 练习3

• 空间复杂度O(1)