Pr-1st-1.1-m04-Slajd57

Funkcje kosztu – oznaczenia

Oznaczmy przez $\Delta _{A}^{\delta }$ zbiór wszystkich poprawnych danych wejściowych $\delta$ algorytmu $A$, a przez ${\mathcal {Z}}_{A}^{*}(\delta )$ - koszt wykonywania tego algorytmu dla danych $\delta$, gdzie $\delta \in \Delta _{A}^{\delta }$ i ${\mathcal {Z}}_{A}^{*}:\Delta _{A}^{\delta }\rightarrow \mathbb {R}$.

Niech ponadto, $\mu$ będzie rozmiarem danych wejściowych $\delta$ (rozmiarem zadania), takim że $\mu ={\mathcal {W}}(\delta )$, gdzie ${\mathcal {W}}:\Delta _{A}^{\delta }\rightarrow \mathbb {N}$, jest zadaną funkcją.

W praktyce, zamiast kosztu ${\mathcal {Z}}_{A}^{*}(\delta )$ stosuje się zwykle jego oszacowanie w funkcji rozmiaru zadania $\mu ={\mathcal {W}}(\delta )$

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