Pr-1st-1.1-m04-Slajd59: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
m Zastępowanie tekstu – „ </math>” na „</math>” |
||
| Linia 4: | Linia 4: | ||
Najczęściej stosowane jest tak zwane odwzorowanie '''pesymistyczne''' (najgorszego przypadku), zdefiniowane w sposób następujący: | Najczęściej stosowane jest tak zwane odwzorowanie '''pesymistyczne''' (najgorszego przypadku), zdefiniowane w sposób następujący: | ||
:<math>\mathcal{Z}_A(\mu) = \sup\{\mathcal{Z}^{*}_A(\delta) : \delta \in \Delta ^{\delta}_A \land \mathcal{W}(\delta) = \mu \} </math> | :<math>\mathcal{Z}_A(\mu) = \sup\{\mathcal{Z}^{*}_A(\delta) : \delta \in \Delta ^{\delta}_A \land \mathcal{W}(\delta) = \mu \}</math> | ||
Funkcja ta odwzorowuje zbiór rozmiarów danych wejściowych algorytmu <math>A</math>(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. | Funkcja ta odwzorowuje zbiór rozmiarów danych wejściowych algorytmu <math>A</math>(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. | ||
Aktualna wersja na dzień 10:52, 5 wrz 2023
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.
