Znaczenie średniej złożoności przy korzystaniu z notacji Big-O

Question

Podczas odpowiadania na this question rozpoczęła się debata w komentarzach dotyczących złożoności QuickSort. Z czasów uniwersyteckich pamiętam, że QuickSort to w najgorszym przypadku: O(n^2), O(n log(n)) w przeciętnym przypadku i O(n log(n)) (ale z bardziej ograniczonym limitem) w najlepszym wypadku.

Potrzebuję poprawnego matematycznego wyjaśnienia znaczenia average complexity, aby jasno wyjaśnić, co to jest dla kogoś, kto wierzy, że notacja big-O może być używana tylko w najgorszym przypadku.

Co pamiętam, jeśli w celu określenia średniej złożoności należy wziąć pod uwagę złożoność algorytmu dla wszystkich możliwych danych wejściowych, policzyć liczbę przypadków zwyrodniałych i normalnych. Jeśli liczba przypadków degeneracji podzielona przez n dąży do 0, gdy n staje się duża, możesz mówić o średniej złożoności ogólnej funkcji dla normalnych przypadków.

Czy ta definicja jest właściwa, czy też definicja przeciętnej złożoności jest inna? A jeśli to prawda, czy ktoś może to bardziej rygorystycznie niż ja?

Answer 1

Jeśli szukasz formalnej definicji, a następnie:

Średnia złożoność jest czas pracy expected dla wejścia losowej.

Answer 2

Średnia analiza case wykonuje następujące operacje:

Take wszystkich wejść o stałej długości (słownie n) Podsumowując wszystkie razy z rzędu wszystkich wystąpień tej długości i budowie średnią.

Problem polega na tym, że prawdopodobnie trzeba będzie wyliczyć wszystkie dane wejściowe o długości n, aby uzyskać średnią złożoność.

Answer 3

Myślę, że twoja definicja jest poprawna, ale twoje wnioski są błędne.

Niekoniecznie prawdą jest, że jeśli odsetek "złych" przypadków zmierza do 0, średnia złożoność jest równa złożoności "normalnych" przypadków.

Załóżmy na przykład, że przypadki 1/(n^2) są "złe", a pozostałe "normalne", a "złe" przypadki wykonują dokładnie (n^4) operacje, podczas gdy "normalne" przypadki mają dokładnie n operacji.

od średniej liczby operacji wymaganych jest równa:

(n^4/n^2) + n(n^2-1)/(n^2) 

Funkcja O (N^2), ale nie O (n).

W praktyce jednak może się okazać, że czas jest wielomianem we wszystkich przypadkach, a odsetek przypadków "złych" kurczy się wykładniczo. To wtedy zignorujesz złe przypadki przy obliczaniu średniej.

Answer 4

Masz rację.

Big O (duży Theta itp.) Służy do mierzenia funkcji. Kiedy piszesz f = O (g), nie ma znaczenia, co oznacza f i g. Mogą być średnia złożoność czas, najgorszy czas złożoności, złożoność przestrzeni oznaczają rozkład liczb pierwszych itp

Najgorszy przypadek złożoność to funkcja, która bierze rozmiarze n, i mówi, co jest maksymalna liczba kroków algorytmu dane wejście o rozmiarze n.

Złożoność średniej wielkości to funkcja, która przyjmuje rozmiar n, i informuje, jaka jest oczekiwana liczba kroków algorytmu danych wejściowych o rozmiarze n.

Jak widać najgorsza i największa złożoność to funkcje, więc możesz użyć dużej litery O, aby wyrazić swój wzrost.

Answer 5

Niech odnoszą Big O Notation in Wikipedia:

Niech f i g są dwie funkcje zdefiniowane na pewnym podzbiorze liczb rzeczywistych. Jeden pisze f(x)=O(g(x)) as x --> infinity jeśli ...

Więc co przesłanką stanach definicji jest to, że funkcja f należy podjąć szereg jako wejście i dają szereg jako wyjście. O jakim numerze wejściowym mówimy? Przypuszczalnie jest to szereg elementów w kolejności do posortowania. O jakiej liczbie wyjściowej możemy mówić? Może to być liczba operacji wykonywanych w celu uporządkowania sekwencji. Ale przestań. Co to jest funkcja? Function in Wikipedia:

funkcją jest relacja między zestawem wejść i wyjść zestawu dopuszczalnych z własności, że każde wejście jest związane z dokładnie jeden wyjściowego.

Czy jesteśmy produkujących exacly jeden wyjście z naszej wcześniejszej defition? Nie, nie robimy tego. Dla danego rozmiaru sekwencji możemy uzyskać dużą różnorodność liczby operacji. Aby zapewnić, że definicja dotyczy naszego przypadku, musimy zredukować zestaw możliwych wyników (liczbę operacji) do pojedynczej wartości. Może to być maksimum ("najgorszy przypadek"), minimum ("najlepszy przypadek") lub średnia.

Wniosek jest taki, że mówienie o najlepszym/najgorszym/przeciętnym przypadku jest poprawne matematycznie i użycie dużej notacji O bez tych w kontekście sortowania złożoności jest nieco niedbałe.

Z drugiej strony, możemy być bardziej precyzyjni i używać dużej notacji Theta zamiast wielkiej notacji O.