Algorytmy o złożoności logarytmicznej i liniowo‑logarytmicznej
Algorytmy o złożoności logarytmicznej i liniowo‑logarytmicznej są bardzo często wynikiem optymalizacji czasowej programów o złożoności liniowej bądź kwadratowej. Charakteryzują się one rozbijaniem głównego problemu na mniejsze i tym samym łatwiejsze do rozwiązania podproblemy.
Przedstawione podejście pozwala na znaczne zmniejszenie liczby wykonywanych operacji. W rezultacie programy, w których zaimplementowano takie algorytmy, mogą działać na dużych zestawach danych wejściowych.
Więcej informacji o złożoności obliczeniowej 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 wykładniczejAlgorytmy o złożoności wykładniczej,
Jak porównywać złożoność obliczeniową?Jak porównywać złożoność obliczeniową?
Scharakteryzujesz algorytmy o logarytmicznej i liniowo‑logarytmicznej złożoności czasowej.
Przeanalizujesz przykłady algorytmów o logarytmicznej i liniowo‑logarytmicznej złożoności czasowej.
Porównasz czas działania programów bazujących na algorytmach o złożoności logarytmicznej i liniowo‑logarytmicznej oraz programów, w których zaimplementowano algorytmy o złożonościach liniowych i kwadratowych.