Nr 01 · Słownik · Teoria informatyki · Algorytmy i struktury danych

Zlozonosc i analiza

14 pojęć w 7 podgrupach, z prostymi definicjami i źródłami.

Granice problemow · 1

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

Klasy zlozonosci · 3

  • 01klasa NPKlasa problemów decyzyjnych, dla których poprawność rozwiązania można zweryfikować w czasie wielomianowym. Niedeterministyczny czas wielomianowy.
  • 02klasa PKlasa problemów decyzyjnych rozstrzygalnych w czasie wielomianowym na deterministycznej maszynie Turinga.
  • 03klasa złożonościZbiór problemów rozwiązywalnych w zadanych granicach zasobów obliczeniowych, np. czasu lub pamięci.

Koszt zamortyzowany · 1

  • 01metoda potencjałuTechnika analizy zamortyzowanej przypisująca strukturze danych funkcję stanu, której zmiana zsumowana z kosztem rzeczywistym operacji daje jej koszt zamortyzowany.

Notacja asymptotyczna · 4

  • 01analiza asymptotycznaBadanie 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.
  • 02notacja Obig-OAsymptotyczne ograniczenie górne tempa wzrostu funkcji; opisuje najgorszy rząd kosztu z dokładnością do stałej. Tzw. duże O.
  • 03notacja OmegaAsymptotyczne ograniczenie dolne tempa wzrostu funkcji; opisuje minimalny rząd kosztu z dokładnością do stałej.
  • 04notacja ThetaŚcisłe asymptotyczne oszacowanie funkcji ograniczające ją zarazem z góry i z dołu tym samym rzędem wzrostu.

Podstawy zlozonosci · 1

  • 01złożoność obliczeniowaMiara ilości zasobów (czasu lub pamięci) potrzebnych do wykonania algorytmu jako funkcja rozmiaru danych wejściowych.

Przypadki analizy · 2

Rekurencje · 2

  • 01metoda drzewa rekursjiTechnika szacowania kosztu rekurencji przez sumowanie pracy na kolejnych poziomach drzewa wywołań rekurencyjnych.
  • 02twierdzenie o rekurencji uniwersalnejmaster theoremSchemat 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.

Pozostałe grupy — Algorytmy i struktury danych

Grupa pojęć · Algorytmy i struktury danych14 haseł