Лекции - Машины Тьюринга. Основы теории вычислимости. Булевы функции и пропозициональные формулы
Подождите немного. Документ загружается.
•
O
•
•
•
O o Ω Θ
f , g : N → R
+
•
f (n) = O(g(n)) ∃c > 0∃n
0
∀n > n
0
, f (n) < cg (n)
•
f (n) = o(g(n)) lim
n→∞
f (n)
g(n)
= 0
•
f (n) = Ω(g (n)) ∃c > 0∃n
0
∀n > n
0
, f (n) > cg (n)
•
f (n) = Θ(g (n))
∃c
1
, c
2
> 0∃n
0
∀n > n
0
, c
1
g(n) < f (n) < c
2
g(n)
f (n) = Θ(g (n)) ⇐⇒
(
f (n) = O(g(n))
g(n) = O(f (n))
•
f (n), g (n) deg f = deg g =⇒ f = Θ(g)
•
f (n), g (n) deg f < deg g =⇒ f = o(g)
•
log
2
n = o(n
k
)
•
log
2
n = Θ(log
a
n) = Θ( n)
•
n
k
= o(2
n
)
•
n
k
= o(n
log n
)
•
O(1)
•
o(1)
•
poly
•
f ∈ poly k ∈ N f = O(n
k
)
•
poly
•
exp
•
f ∈ exp g ∈ poly f = O(2
g(n)
)
•
exp
poly
•
log
•
f ∈ log f = O(logn)
•
poly
•
f ∈ poly k ∈ N f = O(n
k
)
•
poly
•
exp
•
f ∈ exp g ∈ poly f = O(2
g(n)
)
•
exp
poly
•
log
•
f ∈ log f = O(logn)
•
poly
•
f ∈ poly k ∈ N f = O(n
k
)
•
poly
•
exp
•
f ∈ exp g ∈ poly f = O(2
g(n)
)
•
exp
poly
•
log
•
f ∈ log f = O(logn)
•
poly
•
f ∈ poly k ∈ N f = O(n
k
)
•
poly
•
exp
•
f ∈ exp g ∈ poly f = O(2
g(n)
)
•
exp
poly
•
log
•
f ∈ log f = O(logn)
•
poly
•
f ∈ poly k ∈ N f = O(n
k
)
•
poly
•
exp
•
f ∈ exp g ∈ poly f = O(2
g(n)
)
•
exp
poly
•
log
•
f ∈ log f = O(logn)