Czym jest złożoność średniej wielkości

W teorii złożoności obliczeniowej złożoność algorytmu przeciętnego przypadku to ilość pewnego zasobu obliczeniowego (zwykle czasu) używanego przez algorytm , uśredniona dla wszystkich możliwych danych wejściowych. Często kontrastuje się ze złożonością najgorszego przypadku , która uwzględnia maksymalną złożoność algorytmu na wszystkich możliwych danych wejściowych.

Istnieją trzy główne motywacje badania złożoności przeciętnego przypadku. Po pierwsze, chociaż niektóre problemy mogą być trudne do rozwiązania w najgorszym przypadku, dane wejściowe, które wywołują takie zachowanie, mogą rzadko występować w praktyce, więc złożoność przeciętnego przypadku może być dokładniejszą miarą wydajności algorytmu. Po drugie, analiza złożoności przeciętnego przypadku zapewnia narzędzia i techniki do generowania twardych przypadków problemów, które można wykorzystać w obszarach takich jak kryptografia i derandomizacja. Po trzecie, złożoność przeciętnego przypadku umożliwia rozróżnienie najbardziej wydajnego algorytmu w praktyce spośród algorytmów o równoważnej złożoności najlepszego przypadku (na przykład Quicksort ).

Analiza średnich przypadków wymaga pojęcia „średniego” wejścia do algorytmu, co prowadzi do problemu opracowania rozkładu prawdopodobieństwa na wejścia. Alternatywnie można zastosować algorytm randomizowany. Analiza takich algorytmów prowadzi do powiązanego pojęcia oczekiwanej złożoności.

Historia i tło

Wydajność algorytmów dla średniej wielkości przypadków była badana od czasu opracowania nowoczesnych koncepcji wydajności obliczeniowej w latach 50. XX wieku. Wiele z tych początkowych prac koncentrowało się na problemach, dla których znane były już algorytmy czasu wielomianowego w najgorszym przypadku. W 1973 r. Donald Knuth opublikował tom 3 sztuki programowania komputerowego, który obszernie bada wydajność algorytmów dla przypadków przeciętnych dla problemów możliwych do rozwiązania w czasie wielomianu najgorszego przypadku, takich jak sortowanie i znajdowanie median.

Wydajny algorytm dla problemów NP-zupełnych jest ogólnie scharakteryzowany jako taki, który działa w czasie wielomianowym dla wszystkich danych wejściowych; jest to równoznaczne z wymaganiem efektywnej złożoności najgorszego przypadku. Jednak algorytm, który jest nieefektywny dla „małej” liczby danych wejściowych, może nadal być skuteczny dla „większości” danych wejściowych, które występują w praktyce. Dlatego pożądane jest zbadanie właściwości tych algorytmów, w których złożoność przeciętnego przypadku może różnić się od złożoności najgorszego przypadku i znalezienie metod powiązania tych dwóch.

Podstawowe pojęcia złożoności dla przypadków przeciętnych zostały rozwinięte przez Leonida Levina w 1986 roku, kiedy opublikował jednostronicowy artykuł definiujący złożoność i kompletność dla przypadków przeciętnych, jednocześnie podając przykład kompletnego problemu dla distNP, odpowiednika dla przypadków przeciętnych NP.

Więcej na ten temat znajdziesz na stronie: https://generator-liczb.com.pl/