ALG9

59

3.2. Przykład 1: Jeszcze raz funkcja silnia...

Tę poszukiwaną funkcję będziemy zwać złożonością teoretyczną' i z nią najczęściej można się spotkać przy opisach „katalogowych” określonych algorytmów. Funkcja ta jest najczęściej oznaczana przez O. Zastanówmy się, w jaki sposób możemy ją otrzymać.

Istnieją dwa klasyczne podejścia, prowadzące z reguły do tego samego rezultatu: albo będziemy opierać się na pewnych twierdzeniach matematycznych i je aplikować w określonych sytuacjach, albo też dojdziemy do prawidłowego wyniku metodą intuicyjną.

Wydaje mi się, że to drugie podejście jest zarówno szybkie, jak i znacznie przystępniejsze, dlatego skoncentrujemy się najpierw na nim. Popatrzmy w tym celu na tablicę 3-2 zawierającą kilka przykładów „wyłuskiwania” złożoności teoretycznej z równań określających złożoność praktyczną.

Wyniki zawarte w tej tabelce możemy wyjaśnić w następujący sposób: w równaniu pierwszym pozwolimy sobie pominąć stałą 1 i wynik nie ulegnie znaczącej zmianie. W równaniu drugim o wiele ważniejsza jest funkcja kwadratowa niż liniowa zależność od n: podobnie jest w równaniu trzecim, w którym dominuje funkcja 2".

T(n)	O
3n+l	O(n)
n^:-n+1	O(ir)
2"+n^2+4	0(2")

Tabela 3 - 2.

Złożoność teoretyczna algorytmów - przykłady.

Pojęcie funkcji O jest jednak kluczowe, zatem dla ciekawskich warto przytoczyć formalną definicję matematyczną. W tym celu przypomnijmy następujące oznaczenia znane z podręczników analizy matematycznej:

•    N,\R i są zbiorami liczb odpowiednio naturalnych i rzeczywistych (wraz z zerem);

•    Plus (+) przy nazwie zbioru oznacza wykluczenie z niego zera (np.

/V* jest zbiorem liczb naturalnych dodatnich);

•    9\ ’ będziemy oznaczać zbiór liczb rzeczywistych dodatnich lub zero;

•    Znak graficzny t—> oznacza przyporządkowanie;

•    Znak graficzny V należy' czytać jako: dla kctżdego\

I -

¹ Lub klasą algorytmu - określenie zresztą znacznie częściej używane.