Algorytm losowy a algorytm rekurencyjny
Algorytmy zrandomizowane zawierają w swojej logice poczucie losowości poprzez dokonywanie losowych wyborów podczas wykonywania algorytmu. Ze względu na tę losowość zachowanie algorytmu może się zmieniać nawet dla ustalonego wejścia. W przypadku wielu problemów najprostsze i najskuteczniejsze rozwiązania zapewniają algorytmy losowe. 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. Rekursja jest szeroko stosowana do znajdowania rozwiązań problemów w informatyce, a wiele języków programowania wysokiego poziomu obsługuje rekursję.
Co to jest algorytm losowy?
Randomizowane algorytmy uwzględniają poczucie losowości poprzez dokonywanie losowych wyborów, które kierują wykonaniem algorytmu. Odbywa się to zazwyczaj poprzez pobranie zestawu liczb losowych wygenerowanych przez generator liczb pseudolosowych jako dodatkowe dane wejściowe. Z tego powodu zachowanie algorytmu może się zmieniać nawet dla ustalonego wejścia. Quicksort to szeroko znany algorytm wykorzystujący pojęcie losowości, którego czas działania wynosi O (n log n) niezależnie od właściwości wejściowych. Ponadto, losowa metoda budowy przyrostowej jest wykorzystywana do budowy konstrukcji takich jak wypukły kadłub w geometrii obliczeniowej. 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 w projektowaniu algorytmu randomizowanego jest wykonanie analizy asymptotycznej 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 na podstawie jej wcześniejszej wersji. Ważne jest, aby pamiętać, że to odwoływanie się do siebie powinno mieć warunek zakończenia, aby uniknąć odwoływania się na zawsze. Warunek zakończenia jest sprawdzany przed odwołaniem się do siebie. Początkowy krok algorytmu rekurencyjnego jest powiązany z klauzulą podstawową rekurencyjnej definicji problemu. Kroki, które następują po kroku początkowym, są związane z klauzulami indukcyjnymi problemu. Algorytmy rekurencyjne zapewniają prostsze rozwiązanie w wielu sytuacjach i są bliższe naturalnemu sposobowi myślenia niż iteracyjny algorytm dla tego samego problemu. Ale generalnie,algorytmy rekurencyjne wymagają więcej pamięci i są kosztowne obliczeniowo.
Jaka jest różnica między algorytmem randomizowanym a algorytmem rekurencyjnym?
Algorytmy losowe to algorytmy wykorzystujące poczucie losowości poprzez dokonywanie losowych wyborów, które mogą wpłynąć na wykonanie algorytmu, podczas gdy algorytmy rekurencyjne to algorytmy oparte na idei, że rozwiązanie problemu można znaleźć, znajdując rozwiązania mniejszych podproblemów tego samego problemu. Ze względu na losowość w algorytmach losowych zachowanie algorytmu może się zmieniać nawet dla tego samego wejścia (w różnych wykonaniach algorytmu). Nie jest to jednak możliwe w algorytmach rekurencyjnych, a zachowanie algorytmu rekurencyjnego byłoby takie samo dla ustalonych danych wejściowych.
