Powrót

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 1,499. 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ę.

Polecenie 1

Zapisz w postaci listy kroków opisany algorytm, przy założeniu, że komputer wylosował liczbę 265.

RO4CypfjFAAq8
OBIEKT MULTIMEDIALNY KLIKNIJ, ABY OTWORZYĆ NA PEŁNYM EKRANIE
Kliknij, aby rozpocząć
Wystąpił błąd
Spróbuj ponownie później
Polecenie 2

Porównaj swoje rozwiązanie z prezentacją.

R1G5qwm6z4qe21
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

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 n2i. W najgorszym możliwym przypadku powtórzymy tę sama procedurę k razy, aż dojdziemy do zbioru jednoelementowego. Policzmy zatem, ile wynosi k.

n2k=12knklog2n

W najbardziej pesymistycznym przypadku wykonanych zostanie log2n 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(nlog2n), 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
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

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ć log2n 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:

Ilość danych wejściowych

Czas relizacji algorytmu O(log2n)

Czas realizacji algorytmu O(n)

Czas realizacji algorytmu O(nlog2n)

Czas realizacji algorytmu O(n2)

102

109 sekundy

107 sekundy

107 sekundy

105 sekundy

104

108 sekundy

105 sekundy

104 sekundy

0,1 sekundy

106

108 sekundy

103 sekundy

102 sekundy

1000 sekund 17 minut

108

108 sekundy

0,1 sekundy

2 sekundy

107 sekund 115 dni

1010

108 sekundy

10 sekund

330 sekund 5 minut

1011 sekund 3168 lat

1012

108 sekundy

1000 sekund 17 minut

40000 sekund 11 godzin

1015 sekund 31,6 mln lat

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.

Ciekawostka

Istnieje złożoność czasowa O(logn), potocznie nazywana „logarytmem z gwiazdką”. Pod tym pojęciem kryje się odwrotna funkcja Ackermanna, która rośnie niewyobrażalnie powoli. Bardzo często traktuje się logn jako stałą o wartości równej 5.

Słownik

metoda „dziel i zwyciężaj”
metoda „dziel i zwyciężaj”

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

rekurencja
rekurencja

technika programowania polegająca na odwoływaniu się procedur lub funkcji do samych siebie, aż do momentu spełnienia warunku podstawowego

sortowanie przez scalanie
sortowanie przez scalanie

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 n list podrzędnych, z których każda zawiera jeden element;

  • łączenie kolejnych podlist, aby utworzyć nowe posortowane podlisty, aż pozostanie tylko jedna lista

wyszukiwanie binarne
wyszukiwanie binarne

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

złożoność czasowa
złożoność czasowa

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)