Algorytmy o złożoności wykładniczej
Do tej pory zajmowaliśmy się algorytmami o wielomianowych złożonościach czasowych, jednak istnieją problemy, których nie da się tak łatwo rozwiązać. Nazywane są one NP‑zupełnymi i wszystkie znane nam rozwiązania mają złożoność wykładniczą. Do dziś uznawane są one za najgłębsze i najbardziej kłopotliwe problemy otwarte w informatyce.
Więcej informacji o złożoności wykładniczej znajdziesz w e‑materiałach:
Złożoność obliczeniowa algorytmówZłożoność obliczeniowa algorytmów,
Algorytmy o złożoności kwadratowejAlgorytmy o złożoności kwadratowej,
Algorytmy o złożoności logarytmicznej i liniowo‑logarytmicznejAlgorytmy o złożoności logarytmicznej i liniowo‑logarytmicznej,
Jak porównywać złożoność obliczeniową?Jak porównywać złożoność obliczeniową?
Rozpoznasz algorytmy o wykładniczej złożoności czasowej.
Przeanalizujesz działanie przykładowych algorytmów o wykładniczej złożoności czasowej.
Scharakteryzujesz przykłady problemów NP‑zupełnych.