Bài 1: Chứng minh:
O(cf(n)) = O(f(n)) với C là hng số
O(c) = O(1)
Giải:
Chứng minh: O(cf(n)) = O(f(n)) với C là hng số:
Xét t(n) O(f(n))
,
Xét h(n)
Đặt b=
=> O(cf(n))=O(f(n)) ( đpcm ) Chứng minh: O(c)=O(1)
Xét h(n)
k(n)
k(n)
Ta có:
Chn
b)
Chn
d)
Chn
f)
g)
Chn
Câu 3 :
Xét f(n) = 7n
2
; g(n)=n
2
– 80n ; h(n)=n
Chn C = 1, n
0
=1.
g(n) = Of(n)
C/m: f = O(h)
Ta có
Chn C = 7,n
0
= 1
0
k(n)
+
0
-
0
+
Vy ch cn n = 7C là
Đặt n
0
= 7C.
, O(
) ch là mt tp hp.
Cn du “=”
nó th hin là mt đng thức.
V vy
là sai.
Câu 5: Chứng minh
Giải:
2. Chứng minh: f(n)
(1)
Ta có: g(n)
g(n)
(2)
f(n)
( đpcm )
4. O(f(n))=O(g(n)) g(n)
(1)
f(n)
Ta có: g(n)
f(n)
Ta có: g(n)
=>
f(n)
f(n)
Ta có:
f(n)
11)
log
= O(logn), x>0
Ta có:
=> log
= O(logn), x>0
9)
f(n) = O(
)
6)
f(n) = O(g(n)) => a.f(n) = O(g(n)) a> 0
Ta có: f(n)=O(g(n))
f(n)
f(n)
Câu 6: Chứng minh dng giới hn
Giải:
Xét
, p dng tiêu chun D’Alembert, ta có:
Copyright: Tài liệu đại học ©