Co to jest algorytm?
Algorytm to procedura, która krok po kroku ma na celu rozwiązanie problemu. Dobry algorytm powinien być zoptymalizowany pod względem czasu i przestrzeni. Różne typy problemów wymagają różnych typów technik algorytmicznych, które można rozwiązać w najbardziej zoptymalizowany sposób. Istnieje wiele typów algorytmów, ale najważniejsze i podstawowe algorytmy, które należy zastosować, zostały omówione w tym artykule.
1. Algorytm brutalnej siły :
Jest to najbardziej podstawowy i najprostszy typ algorytmu. Algorytm brutalnej siły to proste podejście do problemu, tj. pierwsze podejście, które przychodzi nam na myśl, gdy dostrzeżemy problem. Mówiąc bardziej technicznie, przypomina to iterację każdej dostępnej możliwości rozwiązania tego problemu.
Przykład:
Jeśli jest zamek z 4-cyfrowym PIN-em. Po wybraniu cyfr od 0 do 9 brutalna siła będzie wypróbowywać wszystkie możliwe kombinacje jedna po drugiej, np. 0001, 0002, 0003, 0004 i tak dalej, aż otrzymamy właściwy PIN. W najgorszym przypadku znalezienie właściwej kombinacji zajmie 10 000 prób.
int na znak
2. Algorytm rekurencyjny :
Ten typ algorytmu opiera się na rekurencja . W rekurencji problem rozwiązuje się poprzez rozbicie go na podproblemy tego samego typu i ciągłe wywoływanie własnego self, aż problem zostanie rozwiązany za pomocą warunku podstawowego.
Niektóre typowe problemy rozwiązywane za pomocą algorytmów rekurencyjnych to Silnia liczby , Seria Fibonacciego , Wieża Hanoi , DFS dla wykresu itp.
A) Algorytm dziel i zwyciężaj :
W algorytmach Dziel i zwyciężaj pomysł polega na rozwiązaniu problemu w dwóch sekcjach, pierwsza sekcja dzieli problem na podproblemy tego samego typu. Druga sekcja polega na niezależnym rozwiązaniu mniejszego problemu, a następnie dodaniu połączonego wyniku w celu uzyskania ostatecznej odpowiedzi na problem.
Jednym z typowych problemów rozwiązywanych za pomocą algorytmów dziel i zwyciężaj są Wyszukiwanie binarne , Sortowanie przez scalanie , Szybkie sortowanie, Mnożenie macierzy Strassena itp.
B) Algorytmy programowania dynamicznego :
Ten typ algorytmu jest również znany jako algorytm technika zapamiętywania ponieważ chodzi o to, aby zapisać wcześniej obliczony wynik, aby uniknąć jego ciągłego obliczania. W programowaniu dynamicznym podziel złożony problem na mniejsze nakładające się podproblemy i zapisz wynik do wykorzystania w przyszłości.
Poniższe problemy można rozwiązać za pomocą algorytmu programowania dynamicznego Problem z plecakiem , Ważone planowanie pracy , Algorytm Floyda Warshalla itp.
C) Chciwy algorytm :
W algorytmie Greedy rozwiązanie jest budowane część po części. Decyzja o wyborze kolejnej części podejmowana jest na podstawie tego, że daje ona natychmiastową korzyść. Nigdy nie bierze pod uwagę wyborów, które zostały podjęte wcześniej.
Oto niektóre typowe problemy, które można rozwiązać za pomocą algorytmu zachłannego Algorytm najkrótszej ścieżki Dijkstry , Algorytm Prima , Algorytm Kruskala , Kodowanie Huffmana itp.
D) Algorytm cofania :
W algorytmie Backtracking Algorithm problem jest rozwiązywany w sposób przyrostowy, tj. jest to algorytmiczna technika rozwiązywania problemów rekurencyjnie poprzez próbę zbudowania rozwiązania przyrostowo, element po kawałku, usuwając te rozwiązania, które w żadnym wypadku nie spełniają ograniczeń problemu Punkt czasu.
Niektóre typowe problemy, które można rozwiązać za pomocą algorytmu śledzenia wstecznego, to: Cykl Hamiltona , Problem z kolorowaniem M , Problem z królową N , Problem ze szczurem w labiryncie itp.
3. Randomizowany algorytm :
W algorytmie randomizowanym posługujemy się liczbą losową, która pomaga określić oczekiwany wynik. Decyzja o wyborze losowej liczby tak, aby dawała natychmiastową korzyść
Niektóre typowe problemy, które można rozwiązać za pomocą algorytmu losowego, to Quicksort: W Quicksort używamy losowej liczby do wybierania elementu przestawnego.
4. Algorytm sortowania :
Algorytm sortowania służy do sortowania danych w kolejności rosnącej lub malejącej. Służy także do efektywnego i użytecznego porządkowania danych.
Niektóre typowe problemy, które można rozwiązać za pomocą algorytmu sortowania, to sortowanie bąbelkowe, sortowanie przez wstawianie, sortowanie przez scalanie, sortowanie przez wybór i sortowanie szybkie, to przykłady algorytmu sortowania.
5. Algorytm wyszukiwania :
Algorytm wyszukiwania to algorytm używany do wyszukiwania określonego klucza w określonych posortowanych lub nieposortowanych danych. Niektóre typowe problemy, które można rozwiązać za pomocą algorytmu wyszukiwania, to wyszukiwanie binarne lub wyszukiwanie liniowe, które jest jednym z przykładów algorytmu wyszukiwania.
6. Algorytm mieszający :
Algorytmy mieszające działają tak samo jak algorytm wyszukiwania, ale zawierają indeks z identyfikatorem klucza, tj. Parą klucz-wartość. W hashowaniu przypisujemy klucz do konkretnych danych.
Niektóre typowe problemy można rozwiązać za pomocą algorytmu haszującego podczas weryfikacji hasła.