Paradygmaty analizy złożoności algorytmów

Analiza najgorszych i średnich przypadków to dobrze znane miary złożoności algorytmu. Niedawno wygładzona analiza pojawiła się jako kolejny paradygmat wyjaśniający, dlaczego niektóre algorytmy wykładnicze w najgorszym przypadku działają tak dobrze w praktyce, na przykład algorytm simpleksowy.

Moje pytanie brzmi - czy istnieją jakieś inne paradygmaty do pomiaru złożoności algorytmu? Szczególnie interesują mnie te, które próbują wyjaśnić, dlaczego niektóre algorytmy o złej złożoności najgorszego przypadku sprawdzają się w praktyce.

Przydatne są również naturalne warianty analizy najgorszego przypadku. Być może najbardziej znanym jest sparametryzowana złożoność. Rozważamy tutaj miarę „dwuwymiarową”: zwykłą długość wejściową i pewną dodatkową nieujemną liczbę całkowitą k , parametr. Chociaż algorytm może działać okropnie w najgorszym przypadku (dla wszystkich wartości n i k ), może być tak, że wszystkie przypadki w aplikacji, które wymagają rozwiązania, ten parametr k bywa niski, więc algorytm działa dobrze w tych przypadkach.$n$$k$$n$$k$$k$

Załóżmy na przykład, że chcesz rozwiązać maksymalny zestaw niezależny na pewnej klasie wykresów i opracować interesujący algorytm, który jest zaskakująco szybki. Badając dalej samą klasę wykresów, okazuje się, że wszystkie badane wykresy mają po prostu szerokość . Bodlaender (por. Neidermeier [1]) pokazał, że gdy szerokość wynosi k, Max Independent Set jest ustalony parametr możliwy do przełknięcia : można go rozwiązać w czasie O ( 2 k ( | E | + | V | ) ) . To wyjaśnia, dlaczego Twój algorytm działa dobrze.$10$$O(2^k (|E|+|V|))$

[1] R. Niedermeier, Zaproszenie do algorytmów o stałych parametrach. Seria wykładów Oxford z matematyki i jej zastosowań, Oxford University Press, Oxford, 2006.

Istnieje zamortyzowana złożoność - dlaczego niektóre operacje mogą być kosztowne w najgorszym przypadku, ale jeśli wziąć pod uwagę wiele operacji, średni koszt na operację jest dobry.

Klasycznym przykładem jest struktura danych, która opróżnia się, gdy jest pełna, kopiując wszystkie jej elementy do pewnej pamięci. Operacja kopiowania może być kosztowna, ale nie zdarza się często - musisz wprowadzić wystarczającą liczbę elementów do struktury danych, aby ją sprowokować.