Pr-1st-1.1-m04-Slajd59

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Funkcje kosztu wykonania algorytmów

Funkcje kosztu wykonania algorytmów

Najczęściej stosowane jest tak zwane odwzorowanie pesymistyczne (najgorszego przypadku), zdefiniowane w sposób następujący:

Funkcja ta odwzorowuje zbiór rozmiarów danych wejściowych algorytmu (podzbiór zbioru liczb naturalnych) w zbiór liczb rzeczywistych. Definicja każe interpretować tę funkcję jako miarę złożoności algorytmu dla przypadku najbardziej niekorzystnego, stąd określenie pesymistyczna funkcja kosztu.

W praktyce interesuje nas na ogół nie tyle dokładna wartość , co raczej jej rząd. Dlatego stosuje się powszechnie następujące oznaczenia.


<< Poprzedni slajd | Spis treści | Następny slajd >>