数据结构与算法简述

简介

在计算机科学中，数是核心概念，使用计算机的过程实际上就是对数做各种各样的操作

运用计算机解决一个现实问题时，一般都需要对问题建立数学模型，将其抽象成一个函数 y = f(x), 这种抽象方法掩盖了输入集合x的复杂度，当问题越复杂时，x规模会越来越庞大，x内部的元素越混乱无序，函数f处理的难度变得更大，耗费的资源更多

如何更好地整理数据，高效利用数据，建立有效关联，降低处理难度，尽可能贴近现实问题的具体现象等等，数据结构与算法在此起到作用

在数据结构与算法的介入下，为使用计算机解决现实的问题，需要对问题建立数学模型，设计该模型/系统的交互、输入输出、流程等等，提取问题的关键信息或节点，以某种形式(数据结构)组织起来，用有限的、可行的步骤(算法)模拟问题场景，最后以某种形式(数据结构)呈现出来，给出结果/得出结论/解决问题

《Data Structures and Algorithm Analysis Edition 3.2 (C++ Version)》 —— Clifford A. Shaffer
OI Wiki
灵茶山艾府

数据的组织形式，是抽象数据类型的实现

可以直接作用在输入集合x或f内部的数据，目的是将混乱无序的整理成按某种规则约束呈现的数据

描述数据类型具有的某些特征功能，对外提供可操作该数据类型的接口

作为一个概念，其隐藏了具体实现

与数据结构的关系上，可以这样看:

解决问题的一组操作/指令(一般是数学操作/方法)

参考资料: 复杂度简介 OI Wiki

衡量一个算法效率的重要标准
一般而言，算法性能评估首要考虑的是算法本身在处理特定输入数量时需要的基本操作(Basic Operation)数量/次数
- 基本操作(Basic Operation): 不依赖特定值的操作。例：加法、减法等(求一个数组总和不是，依赖数组元素数量)
衡量算法的性能同时需要考虑数据规模，一般来说，数据规模越大，算法消耗的资源也越多，主要在时间和空间两个层面进行讨论
主要采用 渐进分析 来分析时间和空间随数据规模增长时的趋势，以此评估算法的性能
- 当规模增长时，通过分析变化趋势，更能区分、检测算法可处理的数据规模上限

描述一个函数在输入值趋近于无穷大时的行为

渐进符号
- $\Theta$ (描述函数的渐进上界和渐进下界): 对于函数 $f(n)$ 和 $g(n)$ , $f(n) = \Theta(g(n))$ 当且仅当 $\exist c_{1},c_{2},n_{0}$ , 使得 $\forall n \ge n_{0}, 0\le c_{1}\cdot g(n)\le f(n) \le c_{2}\cdot g(n)$
- $O$ (描述函数的渐进上界): 对于函数 $f(n)$ 和 $g(n)$ , $f(n) = O(g(n))$ 当且仅当 $\exist c,n_{0}$ , 使得 $\forall n \ge n_{0}, 0\le f(n) \le c \cdot g(n)$
- $\Omega$ (描述函数的渐进下界): 对于函数 $f(n)$ 和 $g(n)$ , $f(n) = \Omega(g(n))$ 当且仅当 $\exist c,n_{0}$ , 使得 $\forall n \ge n_{0}, 0\le c \cdot g(n) \le f(n)$
- 此外， $O$ 和 $\Omega$ 还有对应的小写符号 $o$ 和 $\omega$ , 表示非渐进界，在此不展开
一般来说，探索算法可处理的规模上限，即探索函数的渐进上界，所以一般用 $O(f(n))$ 表示复杂度即可

在接下来的笔记中，大致方向是根据在大学上课的内容来展示简单的数据结构和师傅，然后将根据自身的刷题方向罗列算法(本笔记就是为了刷题而建的)，刷题内容参考灵茶山艾府的题单分享｜如何科学刷题？