"Next, please!". Poruszę kolejny temat jaki panuje w algorytmice nawiązując trochę do notacji dużego O. Otóż są takie terminy jak przypadek optymistyczny, przypadek średni i przypadek najgorszy. Opowiemy sobie o jednym i o drugim, i o trzecim, a także kiedy stała wartość robi różnicę w obliczaniu złożoności obliczeniowej. Czy muszę znowu zapraszać?
| Tweet |
CZYM JEST PRZYPADEK OPTYMISTYCZNY, ŚREDNI I NAJGORSZY?
Wiecie już na czym polega notacja dużego O i jak interpretować złożoność obliczeniową algorytmów. Mówiłem, że opisuje ona ile operacji jest potrzebnych dla wskazanych danych wejściowych do opracowania rozwiązania w najgorszym razie. A teraz przyjrzymy się kalkulacji dla przypadku średniego, czyli złożoności stanowiącej największy odsetek wśród wszystkich uruchomień. Pisałem także o tym, że na ogół nie uwzględniamy stałej wartości, bo nie robi ona żadnej różnicy dla naszego wzoru. Czy zawsze tak jest? No...nie!
Są takie przypadki, w których jakaś stała jest istotna dla zmierzenia różnicy pomiędzy poszczególnymi uruchomieniami danego algorytmu. Właśnie wtedy kładziemy nacisk na przypadek średni (ang. "average case"). Jest to złożoność obliczeniowa obrazująca wymaganą liczbę operacji do wykonania względem rozmiaru danych wejściowych jaka pojawia się "z reguły najczęściej". Coś jak średnia z wielu pojedynczych pomiarów. Jeżeli dla przykładu, wynik ukaże się taki sam dla 75 ze 100 osobnych pomiarów algorytmu, to możemy powiedzieć że ten wynik definiuje przypadek średni.
Drugi termin niniejszego artykułu to przypadek najgorszy (ang. "worst-case"). Charakteryzuje się złożonością, która przejawia się w momencie "wyczerpania" liczby operacji niezbędnych do wykonania określonego zadania do granic wytrzymania. Pamiętacie wyszukiwanie binarne? Przypadkiem najgorszym dla zbioru 100-elementowego byłoby maksymalnie 7 iteracji (log2 100 ≈ 7), czyli żeby odnaleźć szukany element w takim zbiorze, program potrzebowałby maksymalnie siedmiu operacji i nigdy nie będzie przekraczać tej liczby!
Jest jeszcze określenie przypadku optymistycznego (ang. "best case"), gdzie notacja opisuje złożoność obliczeniową jaka powstaje w wyniku fenomenalnego działania algorytmu i nie da się osiągnąć jeszcze niższej złożoności. Powołując się raz jeszcze na "binary search", algorytm może odnaleźć szukany element już za pierwszym razem (mimo takiej a nie innej złożoności obliczeniowej)! To właśnie będzie przypadek optymistyczny.
Wszystko na ten temat. Krótko i zwięźle.