数据结构
定义
数据结构的定义包含：
数据对象在计算机中的组织方式；
与数据对象相关联的一个操作集，以及实现这些操作的最高效的算法。
数据对象在计算机中的组织方式，包含两个概念：
一是数据对象集的逻辑结构；
二是数据对象集在计算机中的物理存储结构。
抽象数据类型
抽象数据类型（Abstract Data Type）是一种对“数据类型”的描述，这种描述是“抽象”的。
数据类型描述两方面的内容：
一是数据对象集，二是与数据集相关联的操作集。
抽象 是指，我么描述数据类型的方法不依赖于具体实现的，即数据对象集和操作集的描述与存放数据的机器无关、与数据存储的物理结构无关、与实现操作的算法和编程语言均无关。
抽象数据类型只描述数据对象集合相关操作集“是什么”，并不涉及“如何做到”的问题。
算法
定义
一般而言，算法是一个有限指令集，它接受一些输入（有些情况下不需要输入），产生输出，并一定在有限步骤之后终止。
算法的每一条指令必须有充分明确的目标，不可以有歧义；必须在计算机能处理的范围之内；且其描述不依赖于任何一种计算机语言以及具体的实现手段。
算法不是程序。
两者的区别：
程序可以无限运行（如操作系统），但算法必须在有限步后终止。
算法比程序“抽象”，强调表现“做什么”，而忽略细节性的“怎么做”。
算法复杂程度
比较算法优劣的指标：
（1）空间复杂度 S(n)——根据算法写成的程序在执行时占用存储单元的长度。
空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。
（2）时间复杂度 T(n)——根据算法写成的程序在执行时耗费时间的长度。
时间复杂度过高的低效算法可能导致我们有生之年都等不到运行结果。
在分析一般算法的效率是，我们经常关注下面两中复杂度：
（1）最坏情况复杂度
T
w
o
r
s
t
(
n
)
T_{worst }(n)
Tworst?(n)
（2）平均复杂度
T
a
v
g
(
n
)
T_{avg}(n)
Tavg?(n)
渐进表示法
定义1：
T
(
n
)
=
O
(
f
(
n
)
)
T(n) = O(f(n))
T(n)=O(f(n))
表示存在常数
C
>
0
,
n
0
>
0
C > 0 , n_0 >0
C>0,n0?>0，使得当
n
>
=
n
0
n>=n_0
n>=n0?时有
T
n
<
=
C
(
f
(
n
)
)
Tn<= C(f(n))
Tn<=C(f(n))。
定义2：
T
(
n
)
=
Ω
(
g
(
n
)
)
T(n) = \Omega (g(n))
T(n)=Ω(g(n))
表示存在常数
C
>
0
,
n
0
>
0
C > 0 , n_0 >0
C>0,n0?>0，使得当
n
>
=
n
0
n>=n_0
n>=n0?时有
T
n
>
=
C
(
g
(
n
)
)
Tn>= C(g(n))
Tn>=C(g(n))。
定义3：
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))，那么
（1）两段算法串联在一起的复杂度
T
1
(
n
)
+
T
2
(
n
)
=
m
a
x
(
O
(
f
1
(
n
)
)
,
O
(
f
2
(
n
)
)
)
T_1(n)+T_2(n)=max(O(f_1(n)),O(f_2(n)))
T1?(n)+T2?(n)=max(O(f1?(n)),O(f2?(n)))，即比较慢的那个算法决定了串联后的效率。
（2）两段算法嵌套在一起的复杂度
T
1
(
n
)
?
T
2
(
n
)
=
O
(
f
1
(
n
)
?
f
2
(
n
)
)
T_1(n)*T_2(n)=O(f_1(n)*f_2(n))
T1?(n)?T2?(n)=O(f1?(n)?f2?(n))。 - 若T(n)是关于n的k阶多项式，那么
T
(
n
)
=
Θ
(
n
k
)
T(n)=\Theta(n^k)
T(n)=Θ(nk)。
- 一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度。
- 若干层嵌套循环的时间复杂度等于各层循环次数的乘积再乘以循环体代码的复杂度。
- if-else结构的复杂度取决于if的条件判断复杂度和两个分支的复杂度，总体复杂度取三者中最大。
学习参考资料：
《数据结构》 第2版
|