Co to oznacza oczekiwany czas działania i średni czas działania algorytmu?

Powiedzmy, że chcemy przeanalizować czas działania algorytmów. Czasami mówimy, że chcemy znaleźć czas działania algorytmu, gdy wielkość wejściowa wynosi n, aw najgorszym możliwym przypadku jest oznaczona przez O (n). Czasami jednak widzę książki / artykuły mówiące, że musimy znaleźć oczekiwany czas działania algorytmu. Czasami wykorzystywany jest również średni czas działania .

Co to jest „oczekiwany czas”? W jakich przypadkach warto znaleźć oczekiwany czas zamiast najgorszego przypadku?

Edycja : Myślę, że istnieje subtelna różnica między oczekiwanym czasem działania a średnim czasem działania, ale nie jestem pewien. Poprzez ten post chcę poznać dokładną różnicę, jeśli w ogóle.

Oczekiwany czas to po prostu średni oczekiwany czas działania algorytmu przy użyciu zamierzonego wejścia.

Powiedzmy, że masz kilka milionów rekordów użytkowników i chcesz je posortować, możesz użyć algorytmu, który jest najbardziej odpowiedni dla twoich danych wejściowych i jako taki daje najlepszy oczekiwany czas działania, w przeciwieństwie do algorytmu, który ma lepszy najgorszy czas działania, ale gorszy oczekiwany czas działania.

Czasami na przykład stałe współczynniki złożoności czasowej algorytmu są tak wysokie, że sensowne jest stosowanie algorytmów o gorszej złożoności czasowej, ale o mniejszych stałych czynnikach, ponieważ daje to lepszy oczekiwany czas działania przy niewielkim nakładzie, nawet jeśli uzyskać okropnie lepsze wyniki przy większym nakładzie.

Być może lepszym przykładem byłby klasyczny algorytm szybkiego sortowania, który ma najgorszy czas działania O (n²), ale oczekiwany średni czas działania O (n log n), niezależnie od danych wejściowych . Wynika to z faktu, że algorytm używa (a raczej może , w zależności od implementacji), randomizacji. Jest to tak zwany algorytm losowy . Działa nieco inaczej przy każdym wywołaniu, nawet przy tych samych danych wejściowych. W związku z tym nie ma uniwersalnego wejścia najgorszego przypadku dla implementacji, ponieważ wejście najgorszego przypadku zależy od sposobu, w jaki algorytm wybiera oś obrotu dla podzielenia danych wejściowych. W związku z tym nie można po prostu podać wcześniej określonych danych wejściowych powodujących najgorszy czas działania. Dzieje się tak często w przypadku algorytmów losowych, które mają na celu uzyskanie lepszego oczekiwanego średniego czasu działania niezależnie od danych wejściowych.

Chodzi o użycie odpowiedniego algorytmu dla danych wejściowych.

Oczekiwany czas działania losowego algorytmu jest dobrze zdefiniowaną koncepcją, podobnie jak najgorszy czas działania. Jeśli algorytm jest losowy, jego czas działania jest również losowy, co oznacza, że ​​możemy zdefiniować oczekiwaną wartość jego czasu działania.

Dobrze znanym przykładem jest Quicksort: jeśli wybieramy czopy losowo, możemy udowodnić, że jego oczekiwany czas działania wynosi O (n log n), nawet jeśli najgorszym przypadkiem jest czas działania O (n ^ 2). Przykładem, w którym randomizacja jest bardzo silna, jest najmniejszy problem z otaczającym okręgiem: istnieje prosty algorytm, którego najgorszym przypadkiem jest czas działania O (n ^ 3), ale w oczekiwaniu jego czas działania wynosi tylko O ​​(n).

Średni czas działania jest zwykle używany, gdy mówimy o zachowaniu algorytmu „dla większości danych wejściowych”. Definiujemy jakiś sposób losowego generowania danych wejściowych, na przykład, wypełniamy tablicę losowymi liczbami lub losowo permutujemy liczby od 1 do n (więc nie duplikujemy), lub odwracamy monetę i uzyskujemy zestaw malejący lub rosnący liczby. Średni czas działania algorytmu dla tego losowego rozkładu danych wejściowych jest wówczas oczekiwanym czasem działania algorytmu (w takim przypadku algorytm może nie być losowy, ale dane wejściowe są).

Na przykład: istnieją problemy geometryczne, dla których istnieją algorytmy, które wydają się działać dobrze na pierwszy rzut oka, dopóki nie odkryjesz bardzo dziwnego sposobu dystrybucji, powiedzmy, linii wejściowych. Jeśli założysz, że linie są losowo rozmieszczone, może się zdarzyć, że te dziwne scenariusze są bardzo mało prawdopodobne, więc twój algorytm jest dobry.

Kontrastowanie: oczekiwany czas działania zależy od tego, jak algorytm działa „chyba, że ​​masz pecha” - ponawianie tego samego algorytmu na tym samym wejściu, ale przy różnych losowych wyborach może doprowadzić do jego rozwiązania znacznie szybciej. Średni czas działania mówi o tym, jak dobrze algorytm działa „dla większości danych wejściowych” - ponowna próba zastosowania tego samego algorytmu na tym samym wejściu nie pomoże (chyba że algorytm jest również losowy).