złożoność obliczeniowa

(Informatyka w leśnictwie, oprogramowanie i sprzęt), cechą decydującą dla praktycznej przydatności algorytmu jest jego złożoność obliczeniowa (zwana też kosztem algorytmu), będąca miarą zasobów (np. czasu procesora, pamięci operacyjnej) potrzebnych do rozwiązania za pomocą algorytmu zadania określonego rozmiaru (rozmiarem zadania jest np. długość ciągu liczb do posortowania). Złożoność czasowa algorytmu to funkcja przyporządkowująca rozmiarowi zadania liczbę wykonywanych kolejno w czasie jego rozwiązywania operacji jednostkowych, np. mnożeń, porównań, najbardziej wpływających na czas wykonania algorytmu. Złożoność pamięciowa algorytmu to funkcja przyporządkowująca rozmiarowi zadania maksymalną liczbę komórek pamięci zajętych jednocześnie w trakcie wykonywania algorytmu. Zwykle wyznacza się tzw. rząd złożoności: np. najlepsze algorytmy sortowania mają złożoność czasową rzędu nlogn. Ustalona teoretycznie minimalna złożoność obliczeniowa algorytmu umożliwiającego rozwiązanie zadania określonego typu jest nazywana złożonością zadania.

ŹRÓDŁO (AUTOR)

Encyklopedia PWN

Publikacje powiązane tematycznie

N. WIRTH. Algorytmy + struktury danych = programy, Warszawa 1980.