Przeczytaj
Zgadywanie wylosowanej liczby
Zacznijmy od pewnej zagadki. Wyobraź sobie, że grasz w grę komputerową i twoim zadaniem jest odgadnięcie, jaką liczbę naturalną z zakresu od
Rozwiązanie naiwne o liniowej złożoności czasowej
Jeżeli mamy nieograniczoną liczbę prób, to pierwszym rozwiązaniem, które przychodzi do głowy, jest podawanie po kolei każdej liczby z zakresu od
Rozwiązanie o logarytmicznej złożoności czasowej
Jeżeli interesuje nas przedział od
Zapisz w postaci listy kroków opisany algorytm, przy założeniu, że komputer wylosował liczbę
Porównaj swoje rozwiązanie z prezentacją.
Opisany wyżej algorytm to tzw. wyszukiwanie binarnewyszukiwanie binarne. Dzięki niemu znaleźliśmy wylosowaną liczbę już po 6 próbach. Wykorzystując informację zwrotną przekazywaną przez program, byliśmy w stanie sprowadzić oryginalny problem do mniejszych i łatwiejszych do rozwiązania podproblemów. Technika ta nosi nazwę „dziel i zwyciężaj”; zajmiemy się nią dokładniej w kolejnych e‑materiałach. Teraz udowodnimy, że takie podejście ma logarytmiczną złożoność czasowązłożoność czasową.
Przejdźmy zatem do nieco bardziej ogólnego przypadku. Przeszukujemy zbiór
W najbardziej pesymistycznym przypadku wykonanych zostanie
Sortowanie z wykorzystaniem techniki „dziel i zwyciężaj”
Podczas omawiania złożoności kwadratowej spotkaliśmy się z problemem sortowania
W przypadku opisywanego algorytmu ciąg wejściowy dzieli się na dwa mniejsze ciągi o podobnej liczbie elementów, sortuje je niezależnie od siebie, a następnie scala się je z powrotem. Rozbija się w ten sposób główny problem na mniejsze podproblemy, które traktuje się tak samo.

Sortowaniu przez scalanieSortowaniu przez scalanie poświęcimy osobny e‑materiał, więc nie będziemy na razie zagłębiać się w szczegóły tego mechanizmu porządkowania zbiorów. Wspominamy o nim teraz, ponieważ jest on dobrym przykładem algorytmu o liniowo‑logarytmicznej złożoności czasowej. Wynika to z faktu, że operacja scalania jest liniowa i będziemy ją wykonywać
Przybliżony czas realizacji algorytmów o złożoności logarytmicznej i liniowo‑logarytmicznej
Porównajmy czas wykonywania operacji składających się na algorytmy o logarytmicznej i liniowo‑logarytmicznej złożoności czasowej z czasem realizacji algorytmów o złożonościach poznanych poprzednio:
Ilość danych wejściowych | Czas relizacji algorytmu | Czas realizacji algorytmu | Czas realizacji algorytmu | Czas realizacji algorytmu |
---|---|---|---|---|
Z przedstawionego zestawienia wynika, że algorytmy o złożoności logarytmicznej są wykonywane niezwykle szybko nawet dla dużych ilości danych wejściowych. Natomiast algorytmy o złożoności liniowo‑logarytmicznej są realizowane o wiele szybciej od algorytmów o złożonościach kwadratowych (ale zarazem wolniej od algorytmów liniowych).
Podsumowując, algorytmy logarytmiczne i liniowo‑logarytmiczne charakteryzują się rozbijaniem głównego problemu na mniejsze podproblemy. Jest to dobra metoda optymalizacji czasowej, o której warto pamiętać w trakcie pisania własnych programów.
Istnieje złożoność czasowa
Słownik
metoda, która pozwala na podział problemu na mniejsze, łatwiejsze do rozwiązania podproblemy; po całkowitym rozbiciu problemu oraz rozwiązaniu podproblemów, łączymy je z powrotem w całość i rozwiązujemy cały dany nam problem
technika programowania polegająca na odwoływaniu się procedur lub funkcji do samych siebie, aż do momentu spełnienia warunku podstawowego
jeden z algorytmów sortowania bazujący na metodzie „dziel i zwyciężaj”. Algorytm możemy podzielić na dwa główne etapy:
podzielenie nieposortowanej listy na
list podrzędnych, z których każda zawiera jeden element;łączenie kolejnych podlist, aby utworzyć nowe posortowane podlisty, aż pozostanie tylko jedna lista
metoda odnajdowania elementów w uporządkowanych zbiorach; polega ona na wielokrotnym dzieleniu przeszukiwanego zbioru na dwie równe części i porównywaniu wartości szukanej z elementem znajdującym się w środku dzielonego obszaru
czas niezbędny do rozwiązania określonego problemu, podawany zazwyczaj w liczbach operacji dominujących (zależy ona od ilości danych wejściowych)