|
|
Złożoność obliczeniowa (ang. computational complexity) |
Ważne definicje:
Algorytmy sortowania:
|
Liczba elementarnych operacji, np. porównań, dodawań, mnożeń, przestawień elementów, wykonywanych przez algorytm, podawana na ogół w zależności od długości (ilości) danych. Na przykład liczba porównań potrzebnych do znalezienia najmniejszego (lub największego) elementu w nieuporządkowanym ciągu jest o jeden mniejsza od liczby elementów w tym ciągu. Złożoność algorytmów sortowania jest określana jako liczba wykonywanych porównań i zamian elementów, wyrażona w zależności od liczby porządkowanych elementów. Złożoność najlepszych algorytmów sortowania jest proporcjonalna do nlog2n, gdzie n jest liczbą porządkowanych elementów. Rzeczywisty czas działania algorytmu może być podany dopiero dla konkretnych danych i konkretnego komputera. Inną miarą jakości algorytmu jest jego efektywność określana na podstawie testowania szybkości jego działania na przykładowych danych. Złożoność i efektywność można również zdefiniować dla programów komputerowych. Literatura
|
Strona główna Sortowanie bąbelkowe Sortowanie przez wstawianie Sortowanie przez binarne wstawianie Sortowanie przez wybór Sortowanie przez scalanie Sortowanie przez scalanie - rozszerzone Sortowanie szybkie Sortowanie stogowe Sortowanie stogowe rozszerzone Porównanie algorytmów
