Pr-1st-1.1-m04-Slajd59

Funkcje kosztu wykonania algorytmów

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

${{𝒵}}_A(\mu )=\sup \{{{𝒵}}_A^{*}(\delta ):\delta \in {\mathrm{\Delta }}_A^{\delta }\wedge {𝒲}(\delta )=\mu \}$

Funkcja ta odwzorowuje zbiór rozmiarów danych wejściowych algorytmu $A$(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ść ${{𝒵}}_A(\mu )$, co raczej jej rząd. Dlatego stosuje się powszechnie następujące oznaczenia.

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