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 (N2)
?*— naturalna złożoność O (N * log 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.
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 (N2), 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)
> 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!