Algorytm losowy a rekurencyjny
Algorytmy losowe zawierają poczucie losowości w swojej logice, dokonując losowych wyborów podczas wykonywania algorytmu. Ze względu na tę losowość zachowanie algorytmu może się zmienić nawet dla ustalonego wejścia. W przypadku wielu problemów algorytmy zrandomizowane zapewniają najprostsze i najskuteczniejsze rozwiązania. Algorytmy rekurencyjne opierają się na założeniu, że rozwiązanie problemu można znaleźć, znajdując rozwiązania mniejszych podproblemów tego samego problemu. Rekurencja jest szeroko stosowana do znajdowania rozwiązań problemów w informatyce, a wiele języków programowania wysokiego poziomu obsługuje rekurencję.
Co to jest algorytm randomizowany?
Algorytmy losowe zawierają poczucie losowości, dokonując losowych wyborów, które kierują wykonaniem algorytmu. Zwykle robi się to, biorąc zestaw liczb losowych wygenerowanych przez generator liczb pseudolosowych jako dodatkowe dane wejściowe. Z tego powodu zachowanie algorytmu może się zmienić nawet dla ustalonego wejścia. Quicksort to powszechnie znany algorytm, który wykorzystuje koncepcję losowości i ma czas działania O(n log n) niezależnie od właściwości wejściowych. Co więcej, do budowy konstrukcji takich jak wypukły kadłub w geometrii obliczeniowej stosuje się metodę randomizowanej przyrostowej konstrukcji. W tej metodzie punkty wejściowe są losowo permutowane, a następnie wstawiane jeden po drugim do struktury. Implementacja algorytmu randomizowanego jest stosunkowo prosta niż implementacja algorytmu deterministycznego dla tego samego problemu. Największym wyzwaniem przy projektowaniu algorytmu zrandomizowanego jest wykonanie analizy asymptotycznej dla złożoności czasowej i przestrzennej.
Co to jest algorytm rekurencyjny?
Algorytmy rekurencyjne opierają się na założeniu, że rozwiązanie problemu można znaleźć, znajdując rozwiązania mniejszych podproblemów tego samego problemu. W algorytmie rekurencyjnym funkcja jest definiowana w terminach jej wcześniejszej wersji. Ważne jest, aby pamiętać, że to samoodwołanie powinno mieć warunek zakończenia, aby uniknąć odwoływania się do samego siebie na zawsze. Warunek zakończenia jest sprawdzany przed odniesieniem się. Początkowy krok algorytmu rekurencyjnego jest powiązany z klauzulą bazową rekurencyjnej definicji problemu. Kroki, które następują po kroku początkowym, są powiązane z klauzulami indukcyjnymi problemu. Algorytmy rekurencyjne zapewniają prostsze rozwiązanie w wielu sytuacjach i są bliższe naturalnemu sposobowi myślenia niż algorytm iteracyjny dla tego samego problemu. Ale ogólnie rzecz biorąc, algorytmy rekurencyjne wymagają więcej pamięci i są kosztowne obliczeniowo.
Jaka jest różnica między algorytmem randomizowanym a rekurencyjnym?
Algorytmy losowe to algorytmy, które wykorzystują poczucie losowości, dokonując losowych wyborów, które mogą wpłynąć na wykonanie algorytmu, podczas gdy algorytmy rekurencyjne to algorytmy oparte na założeniu, że rozwiązanie problemu można znaleźć, znajdując rozwiązania mniejszych problemów podrzędnych tego samego problemu. Ze względu na losowość w algorytmach losowych zachowanie algorytmu może się zmienić nawet dla tego samego wejścia (w różnych wykonaniach algorytmu). Ale nie jest to możliwe w algorytmach rekurencyjnych, a zachowanie algorytmu rekurencyjnego byłoby takie samo dla stałych danych wejściowych.
