[小甲鱼] 数据结构与算法笔记01
2020-09-05 本文已影响0人
拜仁的月饼
为什么要写这个系列？
想当年，我的数据结构与算法是通过邓俊辉老师的《算法训练营》，一直在瞎练Leetcode。虽然代码能力有所提高，但举一反三能力还是不太行，换句话说自己对于“提高”这一概念没有什么把握。
看书是很枯燥的事，但看视频会让人上瘾。所以选了个视频来看。
1. 绪论
- 逻辑结构：数据对象中数据元素之间的相互关系
- 物理结构：如何存储数据，有两种：顺序存储与链式存储
- 算法：解决问题的步骤描述，抽象。给定的问题可以用多种方法解决。
- 算法的五个特征：输入、输出、有穷性、确定性、可行性
1.1 四大逻辑结构
- 集合结构：同属一个集合外，没关系
- 线性结构：一对一关系
- 树型结构：层次关系
- 图形结构：多对多关系
1.2 两大物理结构
- 顺序存储：数据元素存放在连续的存储单元中，逻辑关系与物理顺序一致；
- 链式存储：放在任意存储单元里，可连续可不连续，逻辑关系不反映物理顺序，需要一个指针存放地址。
1.3 算法的五个特性
- 输入：有n( n >= 0 )个输入(input)；
- 输出：有n( n >= 1 )个输出；
- 有穷性：步骤必须是有限的；
- 确定性：算法都有确定的含义；
- 可行性：每一步都必须可行。
1.4 算法设计的要求
- 正确性：无语法错误、合法输出有合法输出、非法输入给一个说明、所有的样例都可以跑
- 可读性：便于他人阅读
- Robustness：不会崩溃
- 时间效率高与存储量低：时间复杂度低与空间复杂度低
2. 复杂度
不要用事后统计方法！要事前分析法。从四个方面度量：
- 算法采用的策略、方案；
- 编译产生的代码质量；
- 问题的输入规模;
- 机器执行指令的速度；
判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应关注主项的阶数。
2.1 计算复杂度
定义：O(f(n))
时间复杂度几个阶：
- 常数阶：
O(1) - 线性阶：
O(n) - 平方阶：
O(n ^ 2) - 对数阶：
O(log n)
时间复杂度比较：
空间复杂度：
S(n) = O(f(n))
用空间换时间！
