311
• f (n) = O(n5). На самом деле, f (n) = o(n5).
• f (n) = Ω(n3 log n).
Фактически, f (n) = ω(n3 log n).
• f (n) = Θ(n4).
♦
Основы теории вероятности
Мы предполагаем, что читатель знаком с основами теории вероятности на
уровне, который рассматривается в типичном университетском курсе по дис-
кретной математике. Здесь мы просто напомним читателю о некоторых обозна-
чениях и основных фактах.
If E – это событие, то E¯ обозначает дополнение этого события; т.е., E¯ – это
событие, которое E не происходит.
По определению, Pr[E] = 1 − Pr[E¯]. Если
E1 и E2 являются событиями, то E1 ^ E2 обозначает их конъюнкцию; т.е., E1
^ E2 является таким событием, что происходит как E1, так и E2 . По определе-
нию, Pr[E1 v E2] ≤ Pr[E1]. События E1 и E2 называются независимыми, если
Pr[E1v E2] = Pr[E1] • Pr[E2].
Если E1 и E2 – события, то E1 v E2 обозначает логическое сложение (дизъ-
юнкцию) E1 и E2; то есть, E1 v E2 – такое событие, при котором происходит или
E1 или E2. Из определения следует, что Pr[E1 v E2] ≥ Pr[E1]. Граница объедине-
ния часто является очень полезной верхней границей этой величины.
Достарыңызбен бөлісу: