Przeczytaj
Jak rozpoznawać algorytmy o kwadratowej złożoności czasowej?
Wyobraźmy sobie, że analizujemy pewien algorytm o kwadratowej złożoności czasowej. Niech funkcja wyznacza dokładną liczbę operacji wykonywanych przez program w zależności od ilości danych wejściowych. Przyjmijmy, że ma ona następującą postać:
przy czym jest pewną stałą. Jak w takim razie może być zbudowany algorytm? Spróbujmy zapisać funkcję w nieco inny sposób, a mianowicie:
Przedstawimy kilka propozycji programów, w których zastosowanie znajdą algorytmy o kwadratowej złożoności czasowej.
Obliczanie sumy długości boków i przekątnych figury
Pierwszy program przyjmuje na wejście współrzędne geometryczne punktów, , , , będących wierzchołkami figury wypukłejfigury wypukłej. Na podstawie tych danych wyznaczane są długości wszystkich odcinków , przy czym oraz . Otrzymane wartości są następnie sumowane, dzięki czemu otrzymujemy pożądaną sumę długości boków i przekątnych figury.
![Ilustracja przedstawia pięciokąt o wierzchołkach od A1 do A5. Wierzchołki są wyróżnione jako zamalowane punkty i są ze sobą połączone liniami przerywanymi, które tworzą pięcioramienną gwiazdę. Wnętrze wielokąta jest zamalowane.](https://static.zpe.gov.pl/portal/f/res-minimized/R1GixojeLFAsQ/1617007447/1Q8ymAHXbFkELscJqwa1cbJKDANTdA1U.png)
Zapiszmy odpowiedni algorytm w postaci pseudokodu. Niech Punkty
oznaczają zbiór n
punktów podanych jako dane wejściowe. Dodatkowo niech instrukcja Punkty[i]
oznacza odwołanie się do współrzędnych i
-tego punktu.
Dla każdego punktu spośród n
podanych na wejściu obliczana jest odległość między nim a pozostałymi punktami. Dodatkowo zadbaliśmy o to, aby odległość między każdą parą różnych punktów była liczona dokładnie raz. Dzięki temu w trakcie rozpatrywania i
-tego z kolei punktu, obliczamy odległość dokładnie (n - i)
razy. W rezultacie funkcja opisująca liczbę wykonywanych operacji przybierze następującą postać:
Po skorzystaniu ze wzoru na sumę ciągu arytmetycznego otrzymujemy:
Udowodniliśmy zatem, że nasz algorytm ma kwadratową złożoność czasową.
Rysowanie figur w oknie konsoli
Kolejnym pomysłem na zastosowanie algorytmu o czasowej złożoności kwadratowej jest wypisywanie w oknie konsoli kwadratu zbudowanego ze znaków #
. Jego bok składa się z znaków, przy czym o wartości decyduje użytkownik na początku działania programu.
![Ilustracja przedstawia trzy kwadraty składające się z haszy. W lewym górnym rogu znajduje się kwadrat o wymiarze 5 na 5 haszy z nagłówkiem: "podaj n : 5". Poniżej znajduje się kwadrat o wymiarach 10 na 10 haszy z nagłówkiem "podaj n : 10". Po prawej stronie znajduje się kwadrat 20 na 20 haszy z nagłówkiem "podaj n : 20".](https://static.zpe.gov.pl/portal/f/res-minimized/RFaS6IpLKTIWI/1617007447/EtyrmLrk1lwsT3C8nMYkZOVo8A8F8WWb.png)
Zapiszmy zatem algorytm w postaci pseudokodu.
Dosyć nietypowa może się wydać instrukcja wypisz("\n")
. Symbol \n
jest jednym z symboli sterujących. Mówi on funkcji wypisującej znaki, że należy przejść do nowej linii. Rezultat jest taki sam jak po naciśnięciu klawisza [Enter]
w czasie pracy z edytorem tekstu.
Udowodnienie, że zastosowany algorytm ma kwadratową złożoność czasową jest proste. Zauważmy, że skoro bok kwadratu składa się z znaków #
, to musimy ich wypisać . W konsekwencji należy wykonać około operacji; oznacza to, że mamy do czynienia z kwadratową złożonością czasową.
Sortowanie elementów
![Ilustracja przedstawia eliptyczny zbiór z zielonym wnętrzem. W zbiorze znajdują się białe koła, a w każdym z nich wpisana jest jedna z następujących liczb: 1 po lewo, 4 w dolnej części, 7 po prawo, 10 w górnej części zbioru.](https://static.zpe.gov.pl/portal/f/res-minimized/R1K8S5r88MxPd/1617007448/HbSppA9OBgy0d7T2v1kXSzUBKZeuxeZ2.png)
Ostatnim przykładem jest sortowanie liczb podanych na wejściu przez użytkownika. Ponieważ w czasie obecnej lekcji nie omawiamy sposobów przechowywania danych, nie będziemy zajmować się tym zagadnieniem. Ograniczymy się do przedstawienia idei algorytmu sortowania.
Spośród liczb będzie wybierana najmniejsza. Zostanie ona usunięta z przeszukiwanego zbioru i wypisana na wyjściu. Następnie te same operacje będą powtarzane dla zbiorów złożonych z elementów.
![Ilustracja przedstawia eliptyczny zbiór z zielonym wnętrzem. W zbiorze znajdują się koła, a w każdym z nich wpisana jest jedna z następujących liczb: 1 po lewo, 4 w dolnej części, 7 po prawo, 10 w górnej części zbioru. Koła 4, 7 i 10 są zakolorowane na żółto, a koło 1 jest białe. Po prawej stronie zbioru znajduje się pozioma strzałka skierowana w prawo. Poniżej narysowano podobny eliptyczny zbiór z zielonym wnętrzem. W zbiorze znajdują się koła, a w każdym z nich wpisana jest jedna z następujących liczb: 4 w dolnej części, 7 po prawo, 10 w górnej części zbioru. Koła 7 i 10 są zakolorowane na żółto, a koło 4 jest białe. Po prawej stronie zbioru znajduje się pozioma strzałka skierowana w prawo na koło z liczbą 1 zakolorowane na żółto, które wyjęto ze zbioru. Poniżej narysowano podobny eliptyczny zbiór z zielonym wnętrzem. W zbiorze znajdują się koła, a w każdym z nich wpisana jest jedna z następujących liczb: 7 po prawo, 10 w górnej części zbioru. Koło 10 jest zakolorowane na żółto, a koło 7 jest białe. Po prawej stronie zbioru znajduje się pozioma strzałka skierowana w prawo na koła z liczbami 1 i 4, które są zakolorowane na żółto. Poniżej narysowano podobny eliptyczny zbiór z zielonym wnętrzem. W zbiorze znajduje się białe koło z liczbą 10. Po prawej stronie zbioru znajduje się pozioma strzałka skierowana w prawo na żółte koła z liczbami 1, 4 i 7. Poniżej narysowano podobny eliptyczny zbiór z zielonym wnętrzem. Zbiór jest pusty. Po prawej stronie zbioru znajduje się pozioma strzałka skierowana w prawo na żółte koła z liczbami 1, 4, 7 i 10.](https://static.zpe.gov.pl/portal/f/res-minimized/R18gP1EFgkdHx/1617007448/23Gt3OE2OU4DqCurt72rkIv68mYh6WEr.png)
Niżej znajduje się algorytm przedstawiony w postaci pseudokodu. Niech Liczby
oznaczają zbiór n
liczb podanych na wejściu. Natomiast instrukcja Liczby[i]
oznacza odwołanie się do i
-tej liczby.
Ile operacji wykona program? Znalezienie najmniejszej wartości w zbiorze -elementowym wymaga wykonania porównań. Stosując omawiany algorytm, będziemy wyszukiwać najmniejszy element kolejno w zbiorze -elementowym, następnie w -elementowym i tak dalej. W rezultacie funkcja opisująca liczbę wykonywanych operacji przybierze następującą postać:
Jest to suma ciągu arytmetycznego o wyrazie początkowym równym i różnicy wynoszącej . Korzystając z wzoru na sumę takiego ciągu, otrzymujemy:
Udowodniliśmy zatem, że złożoność czasowa przedstawionego algorytmu sortowania jest kwadratowa.
Przybliżony czas realizacji algorytmów o złożoności kwadratowej
Poznaliśmy i nauczyliśmy się rozpoznawać już trzy złożoności czasowe: stałą, liniową i kwadratową. Korzystając z przybliżenia, zgodnie z którym współczesnym komputerom wykonanie miliarda () operacji zajmuje około sekundę, porównajmy czas działania programów bazujących na algorytmach o różnych złożonościach czasowych.
Liczba danych wejściowych | Czas realizacji algorytmu | Czas realizacji algorytmu |
---|---|---|
sekundy | sekundy | |
sekundy | sekundy | |
sekundy | sekund minut | |
sekundy | sekund dni | |
sekund | sekund lat | |
sekund minut | sekund mln lat |
Dla bardzo małej liczby danych wejściowych różnica między algorytmami liniowymi a kwadratowymi jest naprawdę niewielka. Jednak wraz ze wzrostem liczby danych czas działania programu, w którym zaimplementowano algorytm o kwadratowej złożoności czasowej, rośnie w bardzo dużym tempie. Właśnie dlatego tak ważna jest optymalizacja czasowa programów.
Kryptologia, czyli dziedzina wiedzy zajmująca się przekazywaniem informacji w sposób zabezpieczony przed osobami niepowołanymi, bardzo mocno opiera się na powyższych zależnościach czasowych. Aby złamać 12‑znakowe hasło złożone wyłącznie z małych liter alfabetu angielskiego, trzeba poświęcić aż 30 lat.
Słownik
figura geometryczna, w której zawarty jest każdy odcinek łączący jej dwa dowolne punkty; przykładowymi figurami wypukłymi są trójkąt, elipsa i prostokąt