Algorytm dziel i zwyciężaj
Bardzo popularny paradygmat algorytmiczny, typowy algorytm dziel i zwyciężaj rozwiązuje problem używając następujących trzech kroków:
- Podziel: Rozbij podany problem na podproblemy tego samego typu.
- Podbij: Rekursywnie rozwiąż te podproblemy
- Połącz: Odpowiednio połącz odpowiedzi
Następujące są niektóre standardowe algorytmy, które są algorytmami typu Divide and Conquer:
1 – Wyszukiwanie binarne jest algorytmem wyszukującym. W każdym kroku algorytm porównuje element wejściowy x z wartością elementu środkowego w tablicy. Jeśli wartości się zgadzają, zwraca indeks środka. W przeciwnym wypadku, jeśli x jest mniejsze od elementu środkowego, algorytm szuka po lewej stronie elementu środkowego, w przeciwnym wypadku szuka po prawej stronie elementu środkowego.
2 – Quicksort jest algorytmem sortującym. Algorytm wybiera element pivot, zmienia kolejność elementów tablicy w taki sposób, że wszystkie elementy mniejsze od wybranego elementu pivot przesuwają się na lewą stronę elementu pivot, a wszystkie większe elementy przesuwają się na prawą stronę. Na koniec algorytm rekurencyjnie sortuje podtarcze po lewej i prawej stronie elementu pivot.
3 – Merge Sort jest również algorytmem sortującym. Algorytm dzieli tablicę na dwie połówki, rekurencyjnie je sortuje i na końcu łączy dwie posortowane połówki.
4 – Najbliższa para punktów: Problem polega na znalezieniu najbliższej pary punktów w zbiorze punktów na płaszczyźnie x-y. Problem może być rozwiązany w czasie O(n²) poprzez obliczenie odległości każdej pary punktów i porównanie odległości w celu znalezienia minimum. Algorytm Divide and Conquer rozwiązuje ten problem w czasie O(nLogn).
5 – Algorytm Strassena jest wydajnym algorytmem mnożenia dwóch macierzy. Prosta metoda mnożenia dwóch macierzy wymaga 3 zagnieżdżonych pętli i jest O(n³). Algorytm Strassena mnoży dwie macierze w czasie O(n².8974).
6 – Algorytm Cooley-Tukey Fast Fourier Transform (FFT) jest najczęściej stosowanym algorytmem dla FFT. Jest to algorytm typu „dziel i zwyciężaj”, który działa w czasie O(nlogn).
7 – Algorytm Karatsuba do szybkiego mnożenia: Wykonuje mnożenie dwóch liczb n-cyfrowych w co najwyżej 3n^(log 3) mnożeń jednocyfrowych w ogólności (i dokładnie n^(log3), gdy n jest potęgą 2). Jest więc szybszy od klasycznego algorytmu, który wymaga n² jednocyfrowych iloczynów.
Problem inwersji liczenia
Rozważymy problem pojawiający się w analizie rankingów, które stają się ważne dla wielu obecnych zastosowań. Na przykład, wiele stron w sieci wykorzystuje technikę znaną jako filtrowanie kolaboracyjne, w której próbują dopasować preferencje użytkownika (dotyczące książek, filmów, restauracji) do preferencji innych ludzi w Internecie. Gdy witryna zidentyfikuje osoby o „podobnych” gustach do Twoich – na podstawie porównania jak Ty i oni oceniacie różne rzeczy – może polecić nowe rzeczy, które spodobały się tym innym osobom. Inne zastosowanie pojawia się w narzędziach recta-search w sieci, które wykonują to samo zapytanie w wielu różnych wyszukiwarkach, a następnie próbują syntetyzować wyniki, szukając podobieństw i różnic pomiędzy różnymi rankingami, które wyszukiwarki zwracają.
Podstawowym problemem w aplikacjach tego typu jest problem porównywania dwóch rankingów. Użytkownik klasyfikuje zestaw filmów rt, a następnie system filtrowania kolaboracyjnego konsultuje swoją bazę danych w poszukiwaniu innych osób, które miały „podobne” rankingi. Ale jaki jest dobry sposób, aby zmierzyć liczbowo, jak podobne są rankingi dwóch osób? Oczywiście identyczny ranking jest bardzo podobny, a całkowicie odwrócony ranking jest bardzo różny; chcemy czegoś, co interpoluje przez środkowy region.
Rozważmy porównanie twojego rankingu i rankingu nieznajomego z tego samego zestawu n filmów. Naturalną metodą byłoby oznaczenie filmów od 1 do n zgodnie z twoim rankingiem, a następnie uporządkowanie tych etykiet zgodnie z rankingiem nieznajomego i sprawdzenie, ile par jest „nie w porządku”. Bardziej konkretnie, rozważymy następujący problem. Dany jest ciąg n liczb a1, …, an; założymy, że wszystkie liczby są różne. Chcemy zdefiniować miarę, która powie nam, jak daleko ta lista jest od bycia w porządku rosnącym; wartość miary powinna wynosić 0, jeśli a1 < a2 << an, i powinna wzrastać, gdy liczby stają się bardziej zakodowane.
Naturalnym sposobem kwantyfikacji tego pojęcia jest liczenie liczby inwersji. Mówimy, że dwa indeksy i < j tworzą inwersję, jeśli ai > aj, czyli jeśli dwa elementy ai i aj są „poza kolejnością”. Będziemy dążyć do wyznaczenia liczby inwersji w ciągu a1, …, an.