Badanie złożoności algorytmów cz II 2

Ograniczenia dolne i górne na złożoność:

Rozważmy problem przeszukiwania listy uporządkowanej:

Wiemy, że ważny algorytm przeszukiwania miał złożoność O (N). Wiemy też, że istnieje algorytm lepszy (binarny) o złożoności O (log N). Jeśli założymy, że istnieje algorytm o złożoności optymalnej O (X) dla tego problemu, to obie te złożoności stanowią ograniczenie górne i O (log N) jest bliższe optymalnie niż O (N) — mniejsze ograniczenie górne.

Zatern każde odkrycie algorytmu o złożoności mniejszej niż znamy dotąd ustanawia nowe ograniczenie górne.

Sformułowanie ograniczenia dolnego wymaga dowodu, iż nie da sie zbudować algorytmu o złożoności mniejszej niż określona.

Na przykład ktoś udowodnił, że ograniczenie dolne jest rzędu O (N), praktycznie oznacza to, że każdy algorytm o złożoności większej ale zbliżonej jest wystarczająco sprawny. Ktoś inny może potem udowodnić, że złożoność minimalna jest N * log N jeszcze bardziej zbliżając się do optymalnej (naturalnej) złożoności i zawężając tym samym przedmiot, w którym taka naturalna złożoność tkwi.

O (N3)

O (N2)

?*— naturalna złożoność O (N * log N)

O (N)

Uwaga:

Warto zauważyć, że ograniczenie górne jest związane ze znalezienie konkretnego algorytmu i jego własnościami, ale świadczy o własnościach pewnego zadania algorytmicznego, a nie konkretnego algorytmu. Jeszcze lepiej widać to przy dowodzie ograniczenia dolnego, który jest słuszny dla wszystkich algorytmów tei klasy.

Problemy zamknięte i luki algorytmiczne:

Jeśli ograniczenia górne i dolne sie spotykają ftzn. dysponujemy algorytmem o określonej złożoności i potrafimy udowodnić, że ta złożoność jest minimalną osiągalną (ograniczenie dolne)), to można powiedzieć, że ten problem algorytmiczny jest zamknięty.

Tak jest dla:

a.    przeszukiwania listy nieuporządkowanej — O (N)

b.    przeszukiwania listy uporządkowanej — O (N)

c.    sortowania listy o długości N — O (N * log N), (wykazują ją sortowanie przez scalanie i tzw. samoreorganizujące się sortowanie drzewiaste ( z drzewa długiego i wąskiego, w szerokie i krótkie) — ćwiczenia

Ale są problemy algorytmiczne, gdzie ta luka jest duża: luka algorytmiczna. Jest tak np. dla algorytmu znajdywania najtańszej (najkrótszej) sieci kolejowej między zadanymi miastami — problem minimalnego drzewa rozpinającego. Znamy tu algorytmy o złożoności O (N²), ale potrafimy udowodnić, że ograniczenie dolne jest O (N). Nikt wszakże nie znalazł konkretnego algorytmu o złożoności liniowej. Problem otwarty -» luka algorytmiczna. Zwykle wynika to z naszej niedostatecznej, niezgłębionej wiedzy o problemie. Badania zdążające do zamknięcia tej luki proyyadzone są nadal w ramach tzw. konkretnej teorii złożoności. Okazuje się, że przy pewnym wysiłku problem układania szyn da się ulepszyć aż do osiągnięcia złożoności O (N * log N).

Co wiecei: w poszukiwaniu algorytmu o złożoności liniowej pokazano, że istnieje konkretny algorytm o złożoności O (f (N) * N), gdzie f (N) jest bardzo wolno (znacznie wolniej niż log2 N) rosnącą funkcją N. Dla wybranych wartości N funkcja ta przyjmuje następujące wartości:

N    f (N)

4    2

16    3

64 000    4

> niż całkoyyita liczba cząstek w    znanym    nam Wszechświecie 5

niewyobrażalnie    wielka    liczba    6

Zatem dla wszystkich celóyy praktycznych możnaby przyjąć, że złożoność jest lepsza niż O (5N) a zatem liniowa. Ale w rzeczywistości jednak funkcja f (N) jest funkcją rosnącą, choć niezwykle wolno a nie stałą. Czyli luka teoretycznie istnieje!