Zlozonosc i analiza
14 pojęć w 7 podgrupach, z prostymi definicjami i źródłami.
Przeglądaj kategorię
Granice problemow
Klasy zlozonosci
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.
Koszt zamortyzowany
Notacja asymptotyczna
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.
Podstawy zlozonosci
Przypadki analizy
Rekurencje
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.
Pozostałe grupy — Algorytmy i struktury danych
Chcesz wykorzystać AI w swojej firmie?
Wdrażamy chatboty, agentów głosowych i automatyzacje dla MŚP. Pierwsza konsultacja jest bezpłatna.
Bezpłatna konsultacja