Przez złożoność obliczeniową algorytmu rozumiemy ilość zasobów potrzebnych do jego wykonania. Przez zasoby mamy na myśli czas (złożoność czasową) oraz zużytą pamięć (złożoność pamięciową). Jest to bardzo ważny temat podczas nauki programowania, który każdy programista powinien zrozumieć.

złożonośc obliczeniowa algorytmu

Przed nauką działania algorytmów należy zrozumieć ich złożoność.

Złożoność czasowa

Gdy już zapoznałeś się ze wszystkimi algorytmami opisanymi w poprzednim wpisie, może nasuwać Ci się pytanie: ”Ale po co ich aż tyle?”. Oczywiście, można założyć, iż programiści szukali w wolnej chwili nowych algorytmów, jakby istniejące nie były wystarczające, aby wymyślić wszystkie możliwe opcje sortowania tablicy na świecie. Jednak to niekoniecznie było to. Otóż każdy z opisanych przeze mnie algorytmów ma swoje pewne własności i złożoności. Dobra, teraz pewnie zadajesz sobie kolejne pytanie: ”Czym jest ta złożoność czasowa, o której gość kolejny raz pisze?”. Już śpieszę z wyjaśnieniem. Złożoność czasową mierzymy jako ilość operacji wykonywanych w zależności od danych. Weźmy sobie dla przykładu Bubble Sort’a. Jaka będzie złożoność czasowa takiego programu? Łatwo dostrzec, że mamy tutaj dwie pętle przechodzące po wszystkich elementach w celu ich porównania. Zatem ilość wykonań takich pętli będzie wynosić n2, gdzie n to ilość elementów w tablicy. Zatem złożoność czasowa tego programu będzie wynosić n2. Do zapisu miary złożoności używa się O-notacji, a zatem w tym przypadku będzie to O(n2). Jak łatwo zauważyć i co pewnie część z Was już wie, Bubble Sort nie jest najlepszym i najbardziej optymalnym pomysłem, a wręcz jednym z najgorszych, ponieważ na przykład dla n=1000 będziemy zawsze potrzebować wykonać aż milion operacji porównania elementów, nawet jeśli dane będą od samego początku posortowane w całości. Teraz nasuwa się dodatkowe pytanie, jaki wpływ mają dane początkowe na złożoności algorytmów sortujących?

złożoność algorytmów

Złożoność czasowa algorytmu to ilość operacji wykonywanych w zależności od danych.

Złożoność optymistyczna, pesymistyczna oraz średnia

Poza samym pojęciem złożoności dochodzą do tego kolejne zwroty jak pesymizm, optymizm i średnia. Brzmi strasznie, ale spokojnie zaraz wszystko się rozjaśni. Złożoność pesymistyczna to złożoność najlepsza jaką może osiągnąć algorytm, dla najlepszego rozstawu danych. Dla przykładu posłużmy się algorytmem Insertion Sort’a. Załóżmy, że dane są poukładane w najgorszy dla nas scenariusz, czyli malejąco. Wybierając każdy kolejny element musimy go porównywać ze wszystkimi poprzednimi i za- wsze ustawiać na początek tablicy. W ten sposób otrzymujemy złożoność rzędu O(n2) i jest to nasz przypadek pesymistyczny, zatem jest to złożoność pesymistyczna. Zobaczmy co się stanie gdy będziemy mieć od początku tablicę ułożoną: Każdy element porównujemy tylko z jego poprzednikiem, a zatem złożoność będzie rzędu O(n) i jest to nasza złożoność optymistyczna. Teraz dla porównania weźmy sobie Bubble Sort’a. Tam każdy element musimy zawsze porównać ze wszystkimi, więc zarówno złożoność pesymistyczna jak i optymistyczna będzie rzędu O(n2).

złożoność algorytmów

Złożoność algorytmu może być optymistyczna, pesymistyczna bądź średnia.

Złożoności poszczególnych algorytmów

Wytłumaczenie skąd biorą się złożoności wszystkich poznanych przez Ciebie w tym wpisie algorytmów mogłoby być zbyt ciężkie i przyprawić Cię o ból głowy, więc postanowiłem oszczędzić Ci już tej męki. Także, żeby już nie przedłużyć tak prezentuje się tabela ze złożonościami:

Nazwa

Optymistyczna

Średnia

Pesymistyczna

Bubble Sort

O(n2)

O(n2)

O(n2)

Insertion Sort

O(n)

O(n2)

O(n2)

Selection Sort

O(n2)

O(n2)

O(n2)

Quick Sort

O(nlog(n))

O(nlog(n))

O(n2)

Merge Sort

O(nlog(n))

O(nlog(n))

O(nlog(n))

Heap Sort

O(nlog(n))

O(nlog(n))

O(nlog(n))

”Szybkości” sortowań

Gdy już zechcemy napisać program sortujący tablicę i wykorzystać go na poważnie w praktyce, to raczej nie będziemy używać go dla 10 czy 100 liczb, a raczej dla tablic rzędów milionów elementów. Dla przykładu i łatwych obliczeń ustalmy sobie, że n=106. Wtedy, taki prymitywny Bubble Sort wykonuje aż 1012 operacji porównania, z kolei wykorzystując np. Merge Sort’a będzie ich  około 13  106, co  daje olbrzymią różnicę. Dla przybliżenia tego problemu, sortowanie tablicy miliona elementów z wykorzystaniem Merge Sort’a zajmie niecałą sekundę, zaś dla Bubble Sort’a PONAD GODZINĘ! Stąd płynie ważny wniosek: nie liczy się tylko czy Twój kod działa, lecz też to jak on działa.

złożoność algorytmów

Przy sortowaniu wielu elementów należy rozważyć najlepszy i najszybszy sposób.

© Ambitni Szkoła Informatyki 011111100101(2) | jesteś niemal gotowy!
crossmenu