, , . , , .
, , .
.
:
1. Θ()
f(n) g(n) , n >= 1 ( - ), :
f(n) =Θ(g(n)), c1, 2, n0, , : cl g(n) =< f(n) =< c2 * g(n), n > n0
, g(n) f(n), .. f(n) g(n) .
, f(n) = Θ(g(n)) , g(n) = Θ(f(n)). :
1) f(n)=4n2+nlnN+174 - f(n)= Θ (n2);
2) f(n)=Θ(l) - , f(n) , , f(n) : f(n) = 7+1/n = Θ(1).
2. ( )
Θ, , f(n) g(n) n > n0, :
, O(g(n)) , , , g(n) , , g(n) f(n).
, :
f(n)=l/n, f(n)= 12, f(n)=3n+17, f(n)=nLn(n), f(n)=6n 2+24+77 (n2)
, , f(n)= n2 (n2), .
3. Ω ()
, Ω , .. , , g(n) :
, Ω (nLn(n)) , , g(n) = nLn(n), , .
(Bachman, 1892), Θ,Ω . (Donald Knuth).
, , f(n)=n1+sin(n) g(n)=n .
|
|
, . , Θ , . - , .
, , .
1. ?
2. .
3. ?
4. .
5. .
6. ?
7. -.
8. .
9. .
10. ?
11. ?
12. ?
13. .
14. ? .
15. ? ().
16. ?
17. ?
18. .
19. ?
20. ?