Pr-1st-1.1-m04-Slajd57

Funkcje kosztu – oznaczenia

Oznaczmy przez ${\mathrm{\Delta }}_A^{\delta }$ zbiór wszystkich poprawnych danych wejściowych $\delta$ algorytmu $A$, a przez ${{𝒵}}_A^{*}(\delta )$ - koszt wykonywania tego algorytmu dla danych $\delta$, gdzie $\delta \in {\mathrm{\Delta }}_A^{\delta }$ i ${{𝒵}}_A^{*}:{\mathrm{\Delta }}_A^{\delta }\to \mathbb{ℝ}$.

Niech ponadto, $\mu$ będzie rozmiarem danych wejściowych $\delta$ (rozmiarem zadania), takim że $\mu ={𝒲}(\delta )$, gdzie ${𝒲}:{\mathrm{\Delta }}_A^{\delta }\to \mathbb{\mathbb{N}}$, jest zadaną funkcją.

W praktyce, zamiast kosztu ${{𝒵}}_A^{*}(\delta )$ stosuje się zwykle jego oszacowanie w funkcji rozmiaru zadania $\mu ={𝒲}(\delta )$

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