视频地址

为什么要写这个系列？

想当年，我的数据结构与算法是通过邓俊辉老师的《算法训练营》，一直在瞎练Leetcode。虽然代码能力有所提高，但举一反三能力还是不太行，换句话说自己对于“提高”这一概念没有什么把握。

看书是很枯燥的事，但看视频会让人上瘾。所以选了个视频来看。

1. 绪论

• 逻辑结构：数据对象中数据元素之间的相互关系
• 物理结构：如何存储数据，有两种：顺序存储与链式存储
• 算法：解决问题的步骤描述，抽象。给定的问题可以用多种方法解决。
• 算法的五个特征：输入、输出、有穷性、确定性、可行性

1.1 四大逻辑结构

• 集合结构：同属一个集合外，没关系
• 线性结构：一对一关系
• 树型结构：层次关系
• 图形结构：多对多关系

1.2 两大物理结构

• 顺序存储：数据元素存放在连续的存储单元中，逻辑关系与物理顺序一致；
• 链式存储：放在任意存储单元里，可连续可不连续，逻辑关系不反映物理顺序，需要一个指针存放地址。

1.3 算法的五个特性

• 输入：有n( n >= 0 )个输入(input)；
• 输出：有n( n >= 1 )个输出；
• 有穷性：步骤必须是有限的；
• 确定性：算法都有确定的含义；
• 可行性：每一步都必须可行。

1.4 算法设计的要求

• 正确性：无语法错误、合法输出有合法输出、非法输入给一个说明、所有的样例都可以跑
• 可读性：便于他人阅读
• Robustness：不会崩溃
• 时间效率高与存储量低：时间复杂度低与空间复杂度低

2. 复杂度

不要用事后统计方法！要事前分析法。从四个方面度量：

1. 算法采用的策略、方案；
2. 编译产生的代码质量；
3. 问题的输入规模;
4. 机器执行指令的速度；

判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应关注主项的阶数。

2.1 计算复杂度

定义：O(f(n))

时间复杂度几个阶：

• 常数阶：O(1)
• 线性阶：O(n)
• 平方阶：O(n ^ 2)
• 对数阶：O(log n)

时间复杂度比较：

空间复杂度：
S(n) = O(f(n))

用空间换时间！