[算法] [计算机算法设计与分析笔记（第 5 版）] 第 1 章：算法概述
...
设
F
(
N
)
=
O
(
f
)
F(N) = O(f)
F(N)=O(f)，存在正常数
C
1
C_{1}
C1和自然数
N
1
N_{1}
N1，使得对所有的
N
≥
N
1
N \geq N_{1}
N≥N1，有
F
(
N
)
≤
C
1
f
(
N
)
F(N) \leq C_{1} f(N)
F(N)≤C1f(N)
设
G
(
N
)
=
O
(
g
)
G(N) = O(g)
G(N)=O(g)，存在正常数
C
2
C_{2}
C2和自然数
N
2
N_{2}
N2，使得对所有的
N
≥
N
2
N \geq N_{2}
N≥N2，有
G
(
N
)
≤
C
2
g
(
N
)
G(N) \leq C_{2} g(N)
G(N)≤C2g(N)
令
C
3
=
max
{
C
1
,
C
2
}
C_{3} = \max\set{C_{1} , C_{2}}
C3=max{C1,C2}，
N
3
=
max
{
N
1
,
N
2
}
N_{3} = \max\set{N_{1} , N_{2}}
N3=max{N1,N2}，
h
(
N
)
=
max
{
f
,
g
}
h(N) = \max\set{f , g}
h(N)=max{f,g}，则对所有的
N
≥
N
3
N \geq N_{3}
N≥N3，有
F
(
N
)
≤
C
1
f
(
N
)
≤
C
1
h
(
N
)
≤
C
3
h
(
N
)
F(N) \leq C_{1} f(N) \leq C_{1} h(N) \leq C_{3} h(N)
F(N)≤C1f(N)≤C1h(N)≤C3h(N)，
G
(
N
)
≤
C
2
g
(
N
)
≤
C
2
h
(
N
)
≤
C
3
h
(
N
)
G(N) \leq C_{2} g(N) \leq C_{2} h(N) \leq C_{3} h (N)
G(N)≤C2g(N)≤C2h(N)≤C3h(N)
O
(
f
)
+
O
(
g
)
=
F
(
N
)
+
G
(
N
)
≤
C
3
h
(
N
)
+
C
3
h
(
N
)
=
2
C
3
h
(
N
)
=
O
(
h
)
=
O
(
max
(
f
,
g
)
)
O(f) + O(g) = F(N) + G(N) \leq C_{3} h(N) + C_{3} h(N) = 2 C_{3} h(N) = O(h) = O(\max(f , g))
O(f)+O(g)=F(N)+G(N)≤C3h(N)+C3h(N)=2C3h(N)=O(h)=O(max(f,g))