写在前面
数据结构与算法常被视为一个整体，但它其实是由「数据结构」和「算法」两部分构成。我们很少见到有人将他们完全分开讲解，正是因为二者相辅相成、密不可分：数据结构是为算法的服务的，而算法总要作用在某种特定的数据结构之上。
此外值得注意的是，算法工程师所从事的“算法”工作，与数据结构与算法中的算法中所有的“算法”是两回事。前者的侧重于在数据建模、特征工程和参数调优，计算机更多是作为实现计算的工具；而后者强调的是一种计算机思维——要求我们能够站在计算机的底层视角，对现实问题进行抽象与简化，并运用合理的数据结构设计出高效的解放方案。
数据结构：数据该怎么高效的存
数据结构（data structure）是指数据组织和存储的方式，其核心解决的是数据该怎么存的问题。
常见的数据结构可以分为两大类：
- 线性结构
- 数组（Array）、链表（Linked List）、栈（Stack）、队列（Queue）
- 非线性结构
- 树（Tree）、堆（Heap）、散列表（hash Table）、图（Graph）
设计一个好的数据结构，我们通常需要考虑以下几点：
- 如何节省内存？-> 尽可能减少内存的占用；
- 如何操作更快？-> 优化增删改查等基本操作的效率；
- 如何清晰表达？-> 通过简洁的数据表示支持算法高效运行。
算法：数据该怎么高效的用
算法（algorithm）是指在有限时间内解决特定问题的一组指令或者操作步骤。就像一个靠谱的食谱，只要跟着步骤做，就能在有限时间里做出想要的菜。
一个好的算法，要有这些特质：
- 明确的问题定义：包含清晰的输入和输出定义；
- 可行性：能够在有限步骤、时间、和内存空间下完成；
- 确定性：在相同的输入和运行条件下，输出始终相同；
- 可重复性：任何人依照步骤执行都应该得到相同输出。
我们在设计算法的时候，一般会先后追求两个层面的目标：解决问题和尽可能高效的解决问题。也就是说，我们的目标是设计出“既快又省”的算法，具体点就是：
- 找到问题解法：算法需要在规定的输入范围内可靠地求得问题的正确解。
- 寻找最优解法：同一个问题可能存在多种解法，我们希望找到尽可能高效的算法。
常见的算法思想有不少，比如：
- 递归（Recursion）-> 自己调用自己
- 分治（Divide and Conquer）-> 拆解小问题逐个击破
- 动态规划（Dynamic Programming）-> 记住已经做过的，避免重复劳动
- 贪心算法（Greedy Algorithm）-> 每一步都选当前最好的
- 回溯（Backtracking）-> 试错了就回头
- 枚举（Enumeration）-> 把所有可能都试一遍
复杂度分析：高效判断算法的性价比
复杂度分析，它描述了随着输入数据大小的增加，算法执行所需时间和空间的增长趋势。 说白了就是不看实际运行，就能预估算法随着数据量变大，对执行速度和占用内存有多大影响。
最常用的方法就是大O复杂度表示法，靠它，就能在不用真跑测试的情况下，大致判断一个算法的效率。
复杂度分析的常见概念：
- 最好情况时间复杂度（best case time complexity）
- 在运气最好的时候执行这段代码
- 最坏情况时间复杂度（wrost case time complexity）
- 在运气最背的时候执行这段代码
- 平均情况时间复杂度（average case time complexity）
- 大多数日常情况下，执行这段代码
- 均摊时间复杂度（amortized complexity）
- 又称：摊还分析、平摊分析
- 通过摊还分析法得到的时间复杂度
- 均摊时间复杂度是一种特殊的平均时间复杂度
通常情况下，并不都是需要区分最好、最坏、平均情况时间复杂度的，使用一种复杂度就能满足需求了。
大O复杂度表示法主要看两点：
- 时间复杂度：运行时间随数据规模增长的趋势
- 空间复杂度：占用内存随数据规模增长的趋势
它的核心公式是：$T(n)=O(f(n))$ , 表示执行时间T(n)和某个函数f(n)成正比。
大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随着数据规模增长的变化趋势，故也称为“渐进时间复杂度”。
问题与思考
数据结构与算法到底是什么关系？
数据结构是算法的基石，算法必须依赖数据结构才能发挥作用。反过来，算法又是数据结构的灵魂，没有算法，数据结构也仅是静态的存储单元。它们共同的目标是解决如何更省、更快地存储和处理数据。
怎么判断一个算法好不好？
算法效率的评估通常采用以下两种方法：
事后统计法（又称实际测试法）：
- 一般采取的做法是把算法（代码）运行一遍，根据统计、监控就能得到算法执行的是时间和占用的内存大小。但这种做法有很大的局限性，主要在于，测试结果非常依赖于测试环境（如：运行机器的处理器性能），测试结果受到数据规模大小的影响很大如：对一组数据进行排序，有序的数据一定比无序数据执行效率高，再比如数据量太小的数据，测试结果也无法真实的反应算法的性能）。
复杂度分析法（又称理论估算法）：
- 采用大O复杂度表示法。此方法主要从时间复杂度和空间复杂度两个方面对算法进行理论上的估算，该方法不受环境与具体数据干扰，是更为通用和推荐的评估方式。
常见的复杂度类型有哪些？
按执行效率从高到低排列常见的有：
$$O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)$$
常数阶 < 对数阶 < 线性阶 < 线性对数阶 < 平方阶 < 指数阶 < 阶乘阶
总结一下
- 所有数据结构，本质上都是数组（顺序存储）和链表（链式存储）的组合和扩展。其核心在于如何实现高效的遍历与访问（即增、删、改、查）。
- 所有算法思想，本质上都是对穷举的优化。关键在于如何做到无遗漏、无冗余——也就是在尽可能少的步骤中，找到问题的解。
