Strona główna » Algorytmy » Artykuły » Złożoność Obliczeniowa

Złożoność Obliczeniowa

Wstęp

Przypuśćmy, że pracujemy w zespole programistów, który otrzymał od szefa zadanie do wykonania. Każdy z programistów ma inny pomysł na napisanie algorytmu. Każda z przedstawionych solucji zwraca prawidłowe wyniki. Jednak niektórzy z nich czekali dłużej niż pozostali, aż komputer wyliczył odpowiedź. Szef postanowił wybrać najlepszy algorytm wyliczając jego efektywność na podstawie złożoności obliczeniowej algorytmu.

Złożoność obliczeniowa

W skład złożoności obliczeniowej wchodzi czas wykonywania programu oraz określa liczbę zasobów komputera potrzebnych do wykonania algorytmu.

Złożoność obliczeniową możemy podzielić na dwa główne typy:

W przypadku wyliczania efektywności algorytmu najczęściej bierze się pod uwagę złożoność pesymistyczną. Jest to związane z intencją programisty, aby określić najgorszy przypadek działania. Jeśli algorytm skończy się szybciej to lepiej dla programisty. Jednak jeśli wiemy z jakimi danymi będziemy mieć do czynienie warto wziąć pod uwagę złożoność oczekiwaną.

Powyższy podział możemy zastosować do poniższych kategorii złożoności. W tym przypadku dzielimy rodzaje złożoności na podstawie używanych zasobów komputera:

Wyliczanie złożoności

Złożoność czasowa

Wyznaczając złożoność czasową należy określić operację dominującą. Jest to operacja, która najczęściej jest wykonywana dla każdego elementu danych. Zazwyczaj są to operacje arytmetyczne, przypisania lub porównania (najlepszy przykład to sortowanie). Kolejnym krokiem jest przeanalizowanie działanie algorytmu. Określamy ilość wykonanych operacji dominujących dla określonego zestawu danych. Następnie uogólniamy przypadek dla danych o rozmiarze n.

Jeśli chcemy wyliczyć dokładne złożoności oczekiwane i pesymistyczne to należy rozważyć dla jakich danych algorytm odpowiednio wykonuje się najkrócej / najdłużej. W celu przybliżenia sposobu wyznaczani taki danych warto przyjrzeć się algorytmowi Sortowania Szybkiego, którego złożoność (oczekiwana) to Θ(nlog(n)), ale dla niektórych złożoność (pesymistyczna) wynosi Θ(n2).

Złożoność pamięciowa

Dla określonego zestawu danych określamy ile dla każdego elementu będziemy potrzebowali użyć pamięci w komputerze. W ten sposób będziemy mogli określić np. ile pamięci w komputerze musimy zarezerwować pod działanie naszego programu. W przypadku większych ilości danych złożoność pamięciowa pozwala szybko uzyskać odpowiedź czy program ma szanse na wykonanie się na wybranym komputerze. Problem ten nie występuje w przypadku złożoności obliczeniowej, gdzie dla większego rozmiaru danych będziemy jedynie dłużej czekać na zwrócenie wyniku.

Algorytm optymalny

Najbardziej efektywny jest algorytm, którego złożoność czasowa i pamięciowa jest najniższa. W niektórych przypadkach różne rozwiązania algorytmów pozwalając uzyskać szybkie obliczenie przy dużym zużyciu pamięci, a niektóre pozwalają na wolne wykonanie algorytmu, ale praktycznie nie używając do tego pamięci.

Jeśli algorytm spełnia wszystkie powyższe kryteria to możemy nazwać optymalnym. Oznacza to, że nie istnieje lepszy algorytm / metoda, która rozwiązuje postawiony problem.

Niektóre złożoności czasowe

NazwaΘO złożonościPrzykład
Logarytmicznalognalgorytmy zmniejszające rozmiar podanych danych w każdej iteracji o połowęWyszukiwanie binarne
Pierwiastkowanalgorytmy głównie związane z liczbami, które wykonują operację dominujące w zależności od pierwiastka podanych liczbWyszukiwanie liczb pierwszych
Liniowanalgorytmy, które dla każdej danej wykonują operację dominującąLiniowe wyszukiwanie MAX i MIN
Liniowo-logarytmicznanlog(n)algorytmy dzielące dane w każdej iteracji na dwa równe podzbiory i wykonują na nich operacjeSortowanie przez Scalanie
Kwadratowan2zazwyczaj algorytmy, które wykonują operację dominującą dla każdej pary danychSortowanie Bąbelkowe

Należy pamiętać, że rodzajów złożoności czasowej jest znacznie więcej i zależy to od rozpatrywanego algorytmu