Alg0

60 Rozdział 3. Analiza sprawności algorytmów

•    Znak graficzny 3 należy czytać jako: istnieje',

•    Małe litery pisane kursywą na ogół oznaczają nazwy funkcji (np. g);

•    Dwukropek zapisany po pewnym symbolu S należy odczytywać: S, luki, że... .

Bazując na powyższych oznaczeniach, klasę O dow'olnej funkcji T:N i—> 9v’ możemy zdefiniować jako:

0{T(r0) = {g; T: N h-> R’|(3Me 9* ‘ )(3«₀ e A')(V/t > n, )[|g(«)| ^ \M ■ 7(/z)|]}

Jak wynika z powyższej definicji, klasa O (w'edle definicji jest to zbiór funkcji) ma charakter wielkości asymptotycznej, pozwalającej wyrazić w postaci arytmetycznej wielkości z góry nie znane w postaci analitycznej. Samo istnienie tej notacji pozwala na znaczne uproszczenie wielu dociekań matematycznych, w których dokładna znajomość rozważanych wielkości nie jest konieczna.

Dysponując tak formalną definicją można łatwo udowodnić pewne „oczywiste” wyniki, np.: T(n)^5n’+3n²+2&0(n') (dobieramy doświadczalnie” c=I i n_n=0, wówczas n e 5>i' \ 3tr +2 eO(n³)). W sposób zbliżony można przeprowadzić dowody wielu podobnych zadań.

Funkcja O jest wielkością, której można używać w równaniach matematycznych.

Oto kilka własności, które mogą posłużyć do znacznego uproszczenia wyrażeń je zawierających:

0{f(n))

0{f(n))

0{f{n))

0{f(n) g(n)) /(«)• o(g(n))

c-(j{f(n)) 0[f(n)) + 0[f(n))

o(o(m))

0{.f(nj)0{g{n))

0(f(n)g(nj)

Do ciekawszych należy pierwsza z. powyższych własności, która „niweluje” wpływ wszelkich współczynników o wartościach stałych.

Przypomnijmy elementarny wzór podający zależność pomiędzy logarytmami o różnych podstawach:

log/, *

ln x ln b