附录：所有blog的链接
数据结构学习笔记（1）：基本概念
数据结构学习笔记（2）：线性结构
数据结构学习笔记（3-5）：树
数据结构学习笔记（6-8）：图
数据结构学习笔记（9-10）：排序
数据结构学习笔记（11）：散列查找
数据结构学习笔记（12）：综合习题选讲
第一讲 基本概念
1.1 什么是数据结构
数据结构与算法的定义：
数据对象在计算机中的组织方式，分为逻辑结构、物理存储结构
数据对象必定与一系列加在其上的操作相关联，完成这些操作所用的方法就是算法
抽象数据类型的定义：
数据类型的意义：数据对象集、数据集合相关联的操作集
抽象的意义：
- 描述数据类型的方法不依赖于具体实现口与存放数据的机器无关
- 与数据存储的物理结构无关口
- 与实现操作的算法和编程语言均无关
- 只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题
1.2 什么是算法
算法(Algorithm)的定义：
- 一个有限指令集
- 接受一些输入（有些情况下不需要输入）
- 产生输出
- 一定在有限步骤之后终止
- 每一条指令必须有充分明确的目标，不可以有歧义，计算机能处理的范围之内，描述应不依赖于任何一种计算机语言以及具体的实现手段
算法的衡量指标：
空间复杂度 S ( n ) S(n) S(n)
——根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。
时间复杂度 T ( n ) T(n) T(n)
——根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。
在分析一般算法的效率时，我们经常关注下面两种复杂度
最坏情况复杂度 T w o r s t ( n ) T_{worst}(n) Tworst(n)
平均复杂度 T a v g ( n ) T_{avg}(n) Tavg(n)
T a v g ( n ) ≤ T w o r s t ( n ) T_{avg}(n) \leq T_{worst}(n) Tavg(n)≤Tworst(n)
复杂度的渐进表示法
- 上界： T ( n ) = O ( f ( n ) ) T(n)=O(f(n)) T(n)=O(f(n))表示存在常数 C > 0 C>0 C>0， n 0 > 0 n_0>0 n0>0使得当 n ≥ n 0 n \geq n_0 n≥n0时有 T ( n ) ≤ C ⋅ f ( n ) T(n) \leq C \cdot f(n) T(n)≤C⋅f(n)
- 下界： T ( n ) = Ω ( g ( n ) ) T(n)=\Omega(g(n)) T(n)=Ω(g(n))表示存在常数 C > 0 C>0 C>0， n 0 > 0 n_0>0 n0>0使得当 n > n 0 n>n_0 n>n0时有 T ( n ) ≥ C ⋅ g ( n ) T(n)≥C\cdot g(n) T(n)≥C⋅g(n)
- 等价： T ( n ) = Θ ( h ( n ) ) T(n)=\Theta(h(n)) T(n)=Θ(h(n))表示同时满足 T ( n ) = O ( h ( n ) ) T(n)=O(h(n)) T(n)=O(h(n))和 T ( n ) = Ω ( h ( n ) ) T(n)=\Omega(h(n)) T(n)=Ω(h(n))
寻找最小的上界和最大的上界接近真实情况
常用复杂度分析方法
若两段算法分别有复杂度
T
1
(
n
)
=
O
(
f
1
(
n
)
)
T_1(n)=O(f_1(n))
T1(n)=O(f1(n))和
T
2
(
n
)
=
O
(
f
2
(
n
)
)
T_2(n)= O(f_2(n))
T2(n)=O(f2(n))，则
算法串行复杂度：
T
1
(
n
)
+
T
2
(
n
)
=
max
(
O
(
f
1
(
n
)
)
,
O
(
f
2
(
n
)
)
)
T_1(n)+T_2(n)=\text{max}\left(O(f_1(n)),O(f_2(n))\right)
T1(n)+T2(n)=max(O(f1(n)),O(f2(n)))
算法嵌套复杂度：
T
1
(
n
)
×
T
2
(
n
)
=
O
(
f
1
(
n
)
×
f
2
(
n
)
)
T_1(n)\times T_2(n)=O(f_1(n)\times f_2 (n))
T1(n)×T2(n)=O(f1(n)×f2(n))
一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度
if-else结构的复杂度取决于：if的条件判断复杂度和两个分枝部分的复杂度，总体复杂度取三者中最大
1.3 应用实例：最大子列和问题
评论记录：
回复评论：