数据结构之复杂度衡量

学数据结构的主要原因：

刷Leetcode算法题，无奈做完第一道Leetcode下面的就更本没有思路了，对基本的数据结构不了解，这么重要的课程TMD本科竟然不开，垃圾学校，原来还开C++，到了我们那一届连C++都不开，以至于导致我研一第一学期看SLAM连cout都不知道啥意思，唉……;

互联网企业笔试常常考这些，知道的有点晚，以至于研一下学期招实习的时候连笔试这关都过不了，哈哈，最后去了一个小公司，趁疫情这段时间，提升一下代码能力吧，来面对接下来的秋招。开干，哈哈。

看的书是清华大学灯俊辉编写的数据结构（C++语言版），具体的视频在mooc上、B站上都有，可以看看。这种东西应该早学，影响后期写代码的功底。不瞎求笔笔了，开干。

1、算法：

基于特定的计算模型，解决某一信息处理问题而设计的一个指令序列。

2、算法构成的基本要素

• 输入与输出
• 基本操作、确定性与可行性：当且仅当可以通过程序设计语言精确地描述
• 有穷性与正确性
• 退化与鲁棒性（degeneracy and robustness）
• 重用性：典型形式适用于不同类型基本元素的特性

3、算法效率

• 可计算性
• 难解性
• 计算效率
• 数据结构

4、复杂度度量

4.1 时间复杂度

1、概念：执行时间的变化趋势可以表示为输入规模的一个函数，由于同一算法、同一输入在不同的硬件平台上、不同的操作系统中，所需要的计算时间都不尽相同，一种可行的解决办法将时间复杂度理解为算法中各条指令的执行时间之和。

2、时间复杂度中的三种记号：

记号	衡量情况
$大\sigma记号$大σ记号	算法的最坏情况
$大\Theta记号$大Θ记号	算法的平均情况
$大\Omega记号$大Ω记号	算法的最好情况

4.2 空间复杂度

1、概念：算法所需存储空间的多少。

时间复杂度本身就是空间复杂度的一个天然上界。

4.3 复杂度分析

1、复杂度种类：

• 常数时间复杂度
• 对数时间复杂度
• 线性时间复杂度
• 多项式时间复杂度（前面这几项可以接受）
• 指数时间复杂度（不能称作算法）

2、输入规模：描述输入所需空间规模，影响算法的时间复杂度

重点：如何计算算法的时间复杂度

4.4 递归

1、概念：一种基本而典型的算法设计模式

2、如何计算递归问题的时间复杂度

• 递归跟踪
• 递推方程（微分方程）

3、递归形式：

• 线性递归
• 二分递归
• 多分支递归

4.5 封装

1、概念：将数据结构的外部特性与内部实现分离，提供一致且标准的对外接口，隐藏内部的实现细节。