第二章，第三章作业
第二章，第三章作业
作业
作业
1
1
1.
1.
证明
证明
:
:
n
n
2
2
=
=
O
O
(
(
n
n
3
3
);
);
2.
2.
证明
证明
: 2
: 2
n
n
2
2
+11
+11
n
n
-10=
-10=
O
O
(
(
n
n
2
2
);
);
3.
3.
证明：
证明：
O
O
的以下两个性质
的以下两个性质
O(f(n))
O(f(n))
O(g(n)) = O(f(n)
O(g(n)) = O(f(n)
g(n));
g(n));
O(cf(n)) = O(f(n))
O(cf(n)) = O(f(n))
，其中
，其中
c
c
是一个正的常数；
是一个正的常数；
4.
4.
证明：
证明：
n
n
3
3
O(n
O(n
2
2
)
)
作业
作业
1
1
5.
5.
如果
如果
g
g
(
(
n
n
) =
) =
(
(
f
f
(
(
n
n
))
))
，则
，则
(
(
f
f
(
(
n
n
))+
))+
(
(
g
g
(
(
n
n
)) =
)) =
(
(
f
f
(
(
n
n
))
))
；
；
?
?
6. (
6. (
cf
cf
(
(
n
n
)) =
)) =
(
(
f
f
(
(
n
n
))
))
，其中
，其中
c
c
是一个正的常数
是一个正的常数
;
;
？
？
7. f
7. f
(
(
n
n
) = (
) = (
f
f
(
(
n
n
))
))
?
?
8. (
8. (
f
f
(
(
n
n
))+
))+
(
(
g
g
(
(
n
n
)) =
)) =
(min(
(min(
f
f
(
(
n
n
),
),
g
g
(
(
n
n
))
))
?
?
9.
9.
(
(
f
f
(
(
n
n
))+
))+
(
(
g
g
(
(
n
n
)) =
)) =
(max(
(max(
f
f
(
(
n
n
),
),
g
g
(
(
n
n
))
))
?
?
10.
10.
(
(
f
f
(
(
n
n
))+
))+
(
(
g
g
(
(
n
n
)) =
)) =
(
(
f
f
(
(
n
n
)+
)+
g
g
(
(
n
n
))
))
?
?
若成立，证明之；不成立，举反例。
若成立，证明之；不成立，举反例。
1
1
证明
证明
:
:
n
n
2
2
=
=
O
O
(
(
n
n
3
3
)
)
如果存在两个正常数
如果存在两个正常数
c
c
和
和
n
n
0
0
，对于所有的
，对于所有的
n
n
n
n
0
0
，有
，有
|
|
f(n)
f(n)
|
|
c
c
|
|
g(n)
g(n)
|
|
，则记做
，则记做
f(n)
f(n)
O(
O(
g(n)
g(n)
)
)
证明：
证明：
对于
对于
f(
f(
n
n
)=
)=
n
n
2
2
,g(
,g(
n
n
)=
)=
n
n
3
3
,
,
当
当
c
c
0
0
=1,n
=1,n
0
0
=1
=1
时，
时，
当
当
n ≥ n
n ≥ n
0
0
时，
时，
f(
f(
n
n
) ≤ g(n)
) ≤ g(n)
。
。
命题得证。
命题得证。
2
2
证明
证明
:
:
2
2
n
n
2
2
+11
+11
n
n
-10=
-10=
O
O
(
(
n
n
2
2
)
)
证明：
证明：
对于
对于
f(
f(
n
n
)=2
)=2
n
n
2
2
+11
+11
n
n
-10, g(
-10, g(
n
n
)=
)=
n
n
2
2
,
,
当
当
c
c
0
0
=3,n
=3,n
0
0
=10
=10
时，有
时，有
n≥n
n≥n
0
0
时，
时，
f(
f(
n
n
) ≤ c
) ≤ c
0
0
g(n)
g(n)
命题得证。
命题得证。
评论0
最新资源