数据结构：前言

最近开始复习数据结构与算法，因此这个系列预计会长期更新，以记录复习时的思考、加深对知识的理解。文章力求简洁、通俗易懂！

名词定义

于我而言，学习计算机方面的知识往往遵循“三步走”法则——是什么、怎么做、为什么。那我们首先来看看算法和数据结构是什么。

算法定义

算法是在有限时间内解决特定问题的一组指令或操作步骤。

• 这个特定问题的定义要明确，算法的输入、输出是要有清晰的定义
• 必须在有限步骤、时间和内存空间下完成
• 具有可重复性，对于相同的输入和运行条件，要有相同的输出

数据结构定义

数据结构是计算机中组织和存储数据的方式。

• 占用的空间要尽可能少
• 操作数据时要尽可能快
• 提供简洁的数据表示和逻辑信息，使算法得以高效运行
• 常常需要权衡各方面（如空间大小、访问速度等）

二者关系

• 数据结构就像剧院，算法就像剧本，二者结合在一起才能发挥作用，而计算机（编程语言）则在其中充当演员的角色。同一个剧院可以有不同的剧本上演；同一本剧本可以在不同的剧院上演，但最终表演效果会受到剧院环境的影响。
• 就像剧院和剧本独立于演员一样，数据结构和算法是独立于计算机（编程语言）的

复杂度分析

评估算法效率包括两个维度

• 时间效率：衡量算法运行速度的快慢
• 空间效率：衡量算法占用内存空间的大小

评估算法效率主要有实际测试、理论估算两种方法

实际测试

• 用计算机实际运行某个算法，记录它的运行时间和内存占用情况。但是实际情况中存在着很多的干扰因素和资源限制，因此实际测试存在较大的局限性

理论估算

• 估算算法效率的方法叫做渐进复杂度分析。复杂度分析体现算法运行所需的时间（空间）资源与输入数据大小之间的关系。

描述了随着输入数据大小（体量）的增加，算法执行所需时间和空间的增长趋势

• 因此，复杂度分析关注的不是运行时间或占用空间的具体值，而是时间或空间增长的快慢

• 复杂度又分为时间复杂度、空间复杂度

迭代与递归

算法的复杂度和重复执行的任务密切相关，而重复执行任务和迭代、递归密切相关

迭代

• 迭代循环的复杂度分析较简单，不在此多说

递归

• 递归是一种分而治之思想的体现，通过函数调用自身来解决问题。

• 首先有一个能够直接解决的小问题作为终止条件，面对由多个小问题组成的一个大问题，不断调用自身（递），传入更小或更简化的问题。在不断调用的过程中，问题得到不断简化，最终触发终止条件，从最深层逐层返回（归），返回过程中逐渐解决更大的问题，直到初始的大问题得到解决

• 递归函数的代码主要包含三个要素

  1. 终止条件：决定何时由“递”转“归”
  2. 递归调用：函数调用自身，传入更小或更简化的参数
  3. 返回结果：将当前层的结果返回至上一层

• 每次函数调用都会产生新的栈帧（准备参数、返回地址、old EBP等上下文变量、局部变量），造成额外的时间、空间开销，因此过深的递归可能导致栈溢出

二者关系

• 迭代：自下而上，不断重复最基础的步骤以完成任务
• 递归：自上而下，将原问题分解为与原问题有相同形式的子问题，再将子问题进行分解，直到遇到终止条件（终止条件的结果是明确的）

尾递归

• 尾递归：如果函数在返回前的最后一步才进行递归调用，函数在返回到上一层级后，不用执行其他操作，无需保存上一层函数的上下文，则该函数可以被编译器或解释器优化，使其在空间效率上与迭代相当

时间复杂度

时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大时的增长趋势（因此往往忽略系数、低次项）

• 时间复杂度分析本质上是计算“操作数量函数(n)”的渐进上界

若存在正实数和实数，使得对于所有的 ，均有 ，则可认为给出了的一个渐进上界，记为。

.png)

推算方法

因为分析的是时间增长趋势，所以将任何条件下的一个操作都视作单位时间

1. 统计操作数量
   • 忽略中的常数项
   • 省略所有系数：系数对时间复杂度没有影响
   • 循环嵌套时使用乘法
2. 判断渐进上界
   • 时间复杂度由多项式中的最高阶的项来决定：当趋于无穷大时，最高阶的项将发挥主导作用，其他较低次项的影响可以忽略不计

常见类型

• 常数阶：操作数量与输入数据大小无关，不会随着的变化而变化
• 线性阶：操作数量相对于输入数据大小以线性级别增长。常出现在单层循环
• 平方阶：操作数量相对于输入数据大小以平方级别增长。常出现在内外层循环都为的嵌套循环
• 指数阶：常出现在递归树中
  
• 对数阶：每轮缩减到一半，也常出现于递归函数中，如形成的递归树
• 线性对数阶：常出现在时间复杂度分别为和的嵌套循环中，主流排序算法的时间复杂度通常为线性对数阶，如快速排序、归并排序、堆排序等。
  
• 阶乘阶：对应于全排列问题
  

最差、最佳、平均时间复杂度

算法的时间效率与输入数据的分布有关，“最差时间复杂度”对应渐进上界；“最佳时间复杂度”对应渐进下界

• 最差或最佳时间复杂度只出现于特殊的数据分布，出现概率较小。平均时间复杂度可体现算法在随机输入数据下的运行效率

• 对于较为复杂的算法，平均时间复杂度较难计算，常用最差时间复杂度作为评价标准

空间复杂度

空间复杂度用于衡量算法占用内存空间随着数据量增大时的增长趋势，而不是占用空间的绝对大小

算法相关空间

• 输入空间（不计）：存输入数据
• 暂存空间：存算法运行时的变量、对象、函数上下文等数据
  • 暂存数据（计入）：运行时的常量、变量、对象等
  • 栈帧空间（计入）：调用函数时，保存主调函数的上下文
  • 指令空间（不计）：编译后的语句
• 输出空间（计入）：存输出数据

推算方法

• 统计使用空间大小

• 通常只关注最差（最差输入数据、运行中峰值内存）空间复杂度，必须保证在最差情况下算法也能运行。

常见类型（无线性对数、阶乘）

• 常数阶：循环中声明变量或调用函数会在下一循环释放，不会累积占用空间

• 线性阶：常见于元素数量于成正比的数组、链表、栈、队列等、递归深度为的递归函数

• 平方阶：常见于矩阵和图，元素数量与成平方关系

• 指数阶：常见于二叉树

• 对数阶：常见于分治算法

权衡时间与空间

算法时间复杂度和空间复杂度都达到最佳是理想化的，往往需要在两者之间进行权衡

数据结构分类

常见的数据结构包括数组、链表、栈、队列、哈希表、树、堆、图，可以从逻辑结构和物理结构两个维度进行分类

逻辑结构：线性与非线性

逻辑结构揭示了数据元素之间的逻辑关系

• 线性数据结构：数据、链表、栈、队列、哈希表。元素之间一对一的顺序关系
• 非线性结构：树、堆、图、哈希表。元素之间一对多或多对多关系
  • 树形结构：树、堆、哈希表。一对多
  • 网状结构：图。多对多

物理结构：连续与分散

在计算机中，两种主要的存储硬件设备是：

• 硬盘：长期存储数据、容量较大、访问速度较慢

• 内存：运行程序时暂存数据、容量较小（GB）、访问速度较快

计算机运行起来时，所有程序共享内存资源，物理结构反映了数据在内存中的存储方式，可分为连续空间存储（数组）和分散空间存储（链表）。物理结构从底层决定了数据的访问、更新、增删等操作方法，同时在时间效率和空间效率方面呈现出互补的特点。

所有数据结构都是基于数组（静态数据类型）、链表（动态数据类型）或者二者的组合实现的