Klasyfikacja algorytmów losowych

Z Wikipedii na temat algorytmów losowych

Należy rozróżnić algorytmy, które wykorzystują losowe dane wejściowe w celu zmniejszenia oczekiwanego czasu działania lub zużycia pamięci, ale zawsze kończą się poprawnym wynikiem w ograniczonym czasie, a algorytmy probabilistyczne , które w zależności od losowych danych wejściowych mają szansę wygenerowania niepoprawnego wyniku (algorytmy Monte Carlo) lub niepowodzenia w uzyskaniu wyniku (algorytmy Las Vegas) przez zasygnalizowanie niepowodzenia lub niezakończenie.

1. Zastanawiałem się, jak pierwszy rodzaj „ algorytmów ” wykorzystuje losowe dane wejściowe, aby skrócić oczekiwany czas działania lub zużycie pamięci, ale zawsze kończy się z poprawnym wynikiem w ograniczonym czasie?
2. Jakie są różnice między nim a algorytmami Las Vegas, które mogą nie dać rezultatu?
3. Jeśli dobrze rozumiem, algorytmy probabilistyczne i algorytmy losowe nie są tym samym pojęciem. Algorytmy probabilistyczne to tylko jeden rodzaj algorytmów randomizowanych, a drugi to te, które wykorzystują losowe dane wejściowe, aby skrócić oczekiwany czas działania lub zużycie pamięci, ale zawsze kończą się prawidłowym wynikiem w ograniczonym czasie?

1. $O(n^{2})$$O(n\log n)$$O(n^{2})$$O(n\log n)$ krokach, zawsze z poprawną odpowiedzią.

2. Daje to podzbiór algorytmów Las Vegas. Algorytmy Las Vegas pozwalają również na to, że (z małym prawdopodobieństwem) może w ogóle się nie skończyć - nie tylko zakończyć z nieco większym czasem.

3. Te z kolei są tak naprawdę tylko rodzajem algorytmu Monte Carlo, w którym odpowiedź może być niepoprawna (z małym prawdopodobieństwem), co przynajmniej koncepcyjnie różni się od być może braku odpowiedzi.

Jest cały szereg szczegółów, które oczywiście pominąłem, możesz poszukać klas złożoności ZPP, RP i BPP, które formalizują te pomysły.

Dwa terminy algorytmy randomizowane i algorytmy probabilistyczne są używane w dwóch różnych kontekstach. Algorytmy randomizowane to algorytmy wykorzystujące losowość, w przeciwieństwie do algorytmów deterministycznych, które tego nie robią. Algorytmy probabilistyczne , na przykład algorytmy probabilistyczne do testowania pierwotności, są algorytmami, które wykorzystują losowość i mogą popełnić błąd z pewnym (miejmy nadzieję) małym prawdopodobieństwem.

Należy dokonać istotnego rozróżnienia między algorytmami Monte Carlo i algorytmami Las Vegas . Algorytmy Las Vegas to algorytmy losowe, które zawsze zwracają poprawną odpowiedź, ale ich czas działania zależy od rzutu monetą. Przykładem są algorytmy faktoringu liczb całkowitych - zawsze zwracają prawidłowe współczynniki, ale ich czas działania zależy od losowości. Podając czas działania algorytmu Las Vegas (powiedzmy algorytm faktoringowy), faktycznie podajemy oczekiwany czas działania; jeśli nie będziemy mieli szczęścia, algorytm może działać dłużej.

Z drugiej strony algorytmy Monte Carlo są algorytmem losowym, którego czas działania jest ustalany z wyprzedzeniem. Takie algorytmy mogą popełnić błąd, ale zwykle prawdopodobieństwo błędu jest bardzo niskie. Dobrym przykładem są probabilistyczne testy pierwotności. Algorytmy te są bardzo szybkie, ale mogą powodować błędy. Prawdopodobieństwo błędu jest jednak powolnie niskie, dlatego w praktyce nigdy się nie mylą.

Każdy algorytm Las Vegas można przekonwertować na algorytm Monte Carlo, zatrzymując wykonywanie po wystarczająco długim czasie, więc algorytmy Las Vegas są w pewnym sensie „lepsze” niż algorytmy Monte Carlo.