Zlozonosc i analiza

Minimalny koszt, jakiego wymaga każdy algorytm rozwiązujący dany problem, niezależny od konkretnej implementacji.

Klasa problemów decyzyjnych, dla których poprawność rozwiązania można zweryfikować w czasie wielomianowym. Niedeterministyczny czas wielomianowy.

Klasa problemów decyzyjnych rozstrzygalnych w czasie wielomianowym na deterministycznej maszynie Turinga.

Zbiór problemów rozwiązywalnych w zadanych granicach zasobów obliczeniowych, np. czasu lub pamięci.

Technika analizy zamortyzowanej przypisująca strukturze danych funkcję stanu, której zmiana zsumowana z kosztem rzeczywistym operacji daje jej koszt zamortyzowany.

Badanie zachowania kosztu algorytmu dla rozmiaru wejścia dążącego do nieskończoności, z pominięciem stałych i czynników niższego rzędu.

Asymptotyczne ograniczenie górne tempa wzrostu funkcji; opisuje najgorszy rząd kosztu z dokładnością do stałej. Tzw. duże O.

Asymptotyczne ograniczenie dolne tempa wzrostu funkcji; opisuje minimalny rząd kosztu z dokładnością do stałej.

Ścisłe asymptotyczne oszacowanie funkcji ograniczające ją zarazem z góry i z dołu tym samym rzędem wzrostu.

Miara ilości zasobów (czasu lub pamięci) potrzebnych do wykonania algorytmu jako funkcja rozmiaru danych wejściowych.

Wyznaczanie maksymalnego kosztu algorytmu po wszystkich wejściach danego rozmiaru.

Wyznaczanie oczekiwanego kosztu algorytmu względem rozkładu prawdopodobieństwa danych wejściowych.

Technika szacowania kosztu rekurencji przez sumowanie pracy na kolejnych poziomach drzewa wywołań rekurencyjnych.

Schemat dający asymptotyczne rozwiązanie rekurencji postaci T(n)=aT(n/b)+f(n) typowej dla algorytmów dziel i zwyciężaj. Tzw. master theorem.