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 $1$ do $1000$ wylosował komputer. Masz nieograniczoną liczbę prób i za każdym razem otrzymujesz informację zwrotną o tym, czy wybrana przez ciebie liczba jest mniejsza, czy też większa od wylosowanej.

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 $1$ do $1000$. Jednak wymagałoby to od nas dużego zapasu cierpliwości; w najgorszym przypadku musielibyśmy podać kolejno aż tysiąc liczb. Zastanówmy się zatem, jak moglibyśmy ulepszyć nasze rozwiązanie. Może warto skorzystać z otrzymywanej informacji zwrotnej?

Rozwiązanie o logarytmicznej złożoności czasowej

Jeżeli interesuje nas przedział od $1$ do $1000$, to możemy podać liczbę znajdującą się w jego środku, czyli $500$. Załóżmy, że nie trafiliśmy i otrzymaliśmy informację zwrotną, zgodnie z którą poszukiwana liczba jest mniejsza od podanej. Wiemy wtedy, że znajduje się ona gdzieś w przedziale $\langle 1, 499\rangle$. W tak prosty sposób zmniejszyliśmy przeszukiwany obszar o połowę! Możemy za każdym razem podawać liczbę ze środka interesującego nas przedziału i dzięki informacji zwrotnej zmniejszać go, aż w końcu trafimy na poszukiwaną liczbę.

Opisany wyżej algorytm to tzw. wyszukiwanie binarnewyszukiwanie 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ść czasowazłożoność czasową.

Przejdźmy zatem do nieco bardziej ogólnego przypadku. Przeszukujemy zbiór $n$ liczb naturalnych i po każdej próbie zmniejszamy jego rozmiar o połowę. Zatem w $i$-tym kroku będziemy mieli do czynienia ze zbiorem o wielkości $\frac{n}{2^i}$. W najgorszym możliwym przypadku powtórzymy tę sama procedurę $k$ razy, aż dojdziemy do zbioru jednoelementowego. Policzmy zatem, ile wynosi $k$.

W najbardziej pesymistycznym przypadku wykonanych zostanie $\log_2n$ iteracji. Algorytm ma zatem logarytmiczną złożoność czasową.

Sortowanie z wykorzystaniem techniki „dziel i zwyciężaj”

Podczas omawiania złożoności kwadratowej spotkaliśmy się z problemem sortowania $n$ liczb. Okazuje się, że do jego rozwiązania również możemy wykorzystać metodę „dziel i zwyciężaj”. Uzyskamy dzięki temu algorytm rekurencyjnyrekurencjarekurencyjny o złożoności czasowej $O(n\log_2n)$, nazywany sortowaniem przez scalaniesortowanie przez scalaniesortowaniem przez scalanie (ang. merge sort).

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.

R1OO53dHCVhdP

Rozdzielony ciąg wejściowy na mniejsze ciągi. Mamy tu dwie ścieżki podziałów. Ścieżka pierwsza. Ciąg 5217896 rozbity jest na 5217, ciąg 5217 rozbity jest na 52 i na 17. 52 rozbite jest na 5 i 2. Komenda "SCAL" daje nam 25. Z kolei 17 rozbite jest na 1 i 7. Komenda "SCAL" daje nam 17. Mamy więc 25 i 17. Komenda scal daje nam 1257. Jest to przedostatni krok tej ścieżki. Druga ścieżka. Od ciągu wyjściowego 52174896 mamy drugie rozbicie na 4896. Ten ciąg rozbity jest na dwa ciągi: 48 i 96. 48 rozbite jest na 4 i 8. Komenda "scal" daje nam 48. Ciąg 96 rozbity jest na 9 i 6. Komenda "SCAL" daje nam 69. Mając ciągi 48 i 69 wykonujemy komendę "SCAL", otrzymując 4689. Krok ostatni. Mamy z pierwszej ścieżki ciąg 1257 i z drugiej ścieżki 4689. Komenda "SCAL" daje nam ciąg 123456789.

Sortowaniu przez scalaniePNHdnGJ4ISortowaniu 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ć ${\log }_{2}n$ razy.

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:

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.

Słownik