数据结构与算法系列文章目录
【数据结构与算法】data structures & algorithms 第一章：复杂度分析
【数据结构与算法】data structures & algorithms 第二章：基本概念
【数据结构与算法】data structures & algorithms 第三章：线性数据结构
【数据结构与算法】data structures & algorithms 第四章：树的数据结构
【数据结构与算法】data structures & algorithms 第五章：图的数据结构
【数据结构与算法】data structures & algorithms 第六章：各类常见的排序算法
【数据结构与算法】data structures & algorithms 第七章：散列表算法的初步运用
【数据结构与算法】data structures & algorithms 第八章：红黑树的理解与使用
一、时间复杂度
-
简介
- 不同计算机的软硬件环境不同，所以不能通过计算机上运行所消耗的时间来度量；
- 一般地，时间复杂度是用总的执行次数来间接表示程序的运行时间，这样根据不同性能的计算机，单位时间内执行速度来度量时间的消耗；
- 数据结构中，每条语句的执行次数，被称为该语句的频度；在计算代码的频度时，一般会得到一个式子，此时需要简化，取最大的因子；如有
2
n
+
3
n
2
+
1
2n + 3n^2 + 1
2n+3n2+1?，通过
n
→
∞
n\rightarrow \infty
n→∞,我们可以把式子简化为
n
2
n^2
n2?；
- 一般地，习惯用大O表示法，表达
T
(
n
)
T(n)
T(n)的时间复杂度，即
O
(
频
度
)
O( 频度 )
O(频度)；一般情况下，以最坏情况的频度作为时间复杂度；
-
计算
- 寻找算法的基本语句：执行次数最多的语句，通常在最内侧循环的循环体中；
- 将基本语句执行次数的数量级放入大O中；
- 常见的时间复杂度
O
(
1
)
<
O
(
log
?
n
)
<
O
(
n
)
<
(
n
log
?
n
)
<
O
(
n
2
)
<
o
(
n
3
)
<
?
<
O
(
2
n
)
<
O
(
n
!
)
<
O
(
n
n
)
O(1) < O(\log n) < O(n) < (n\log n) < O(n^2) < o(n^3) < \cdots < O(2^n) < O(n!) < O(n^n)
O(1)<O(logn)<O(n)<(nlogn)<O(n2)<o(n3)<?<O(2n)<O(n!)<O(nn)
一般地，算法没有循环体的时间复杂度为
O
(
1
)
O(1)
O(1)，即常数时间；
O
(
log
?
n
)
,
O
(
n
)
,
O
(
n
log
?
n
)
,
O
(
n
2
)
,
O
(
n
3
)
O(\log n),O(n),O(n\log n),O(n^2),O(n^3)
O(logn),O(n),O(nlogn),O(n2),O(n3)等称为多项式时间，带有这类时间复杂度的算法才算是可执行的有效算法；
O
(
2
n
)
,
O
(
n
!
)
O(2^n),O(n!)
O(2n),O(n!)等被称为指数时间；
二、空间复杂度
-
简介
- 算法运行过程中临时占用空间大小的度量，用
S
(
n
)
S(n)
S(n)定义；
- 一般地，只注意定义变量的语句；
- 计算复杂度时，观察与n的变化关系，如
i
n
t
??
a
=
0
int \ \ a = 0
int??a=0，与n无关，
i
n
t
??
b
[
n
]
int \ \ b[n]
int??b[n]，与n有关；
-
计算
- 程序占用存储空间与输入值无关，则为
O
(
1
)
O(1)
O(1)；
- 如果随着输入值n的增大，申请的临时空间成线性增长，则为
O
(
n
)
O(n)
O(n)；
- 如果随着输入值n的增大，申请的临时空间成
n
2
n^2
n2增长，则为
O
(
n
2
)
O(n^2)
O(n2)；
- 如果
?
\cdots
?，
?
\cdots
?成
n
3
n^3
n3增长，则为
O
(
n
3
)
O(n^3)
O(n3)；
|