algorytm.org

Złożoność obliczeniowa

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Złożoność obliczeniowa
Ocena użytkowników:***** / 181
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 01 sierpnia 2005 22:22

Jest to jeden z najważniejszych parametrów charakteryzujących algorytm. Decyduje on o efektywności całego programu. Podstawowymi zasobami systemowymi uwzględnianymi w analizie algorytmów są czas działania oraz obszar zajmowanej pamięci. Na złożoność czasową składają się dwie wartości: pesymistyczna, czyli taka, która charakteryzuje najgorszy przypadek działania oraz oczekiwana. Najczęściej algorytmy mają złożoność czasową proporcjonalną do funkcji:
  • log(n)- złożoność logarytmiczna
  • n - złożoność liniowa
  • nlog(n) - złożoność liniowo-logarytmiczna
  • n2 - złożoność kwadratowa
  • nk - złożoność wielomianowa
  • 2n - złożoność wykładnicza
  • n! - złożoność wykładnicza, ponieważ n!>2n już od n=4

Zobacz też rzędy wielkości funkcji

Poprawiony: 15 sierpnia 2005 23:53
Komentarze
photo
-25 # Łukasz 2010-01-25 10:19
A np kolorowanie wierzchołków grafu!?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-7 # ! 2012-02-24 09:30
Cytuję Łukasz:
A np kolorowanie wierzchołków grafu!?


Tak tak dokładnie tak
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-12 # boss 2011-01-04 23:11
moze ktos uporządkować te złożoności czasowe od najmniejszej do największej
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+38 # Tomasz Lubiński 2011-01-05 13:20
Z grubsza złożoności można posortować następująco (od najlepszej (najmniejszej)) :
log(n)
n
nlog(n)
n^2
n^3
...
2^n
3^n
...
n!

Na załączonym wykresie widać jak czas wykonania programu rośnie w zależności od wielkości rozwiązywanego problemu.

Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+15 # SP 2011-05-17 19:33
Sorki boss ale to przecież mogłeś sam policzyć podstawiając coś za n, już ludzie kompletnie nic nie myślicie albo jesteście leniwi
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-9 # Hubson 2011-09-03 16:06
Pierwsza sprawa jest taka ze wartość pesymistyczna i oczekiwana to nie wszystkie występuje też wartość optymistyczna. Co więcej nie napisałeś nic o wyliczaniu złożoności więc nie mam pojęcia po co jest twój wpis. Nawet nie podałes nazw poszczególnych oszacowań , nie podałeś żadnych wykresów , wg. mnie albo robisz coś dobrze albo nie robisz tego wcale .
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+9 # AntiHubson 2013-05-25 14:30
Cytuję Hubson:
Nawet nie podałes nazw poszczególnych oszacowań , nie podałeś żadnych wykresów , wg. mnie albo robisz coś dobrze albo nie robisz tego wcale .

Ty Hubson nie zrobiłeś nic i krytykujesz innych. Czekam na link do twojego artykułu, zobaczymy jaki jesteś mocny.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz