Algorytm Dziel i Rządź to strategia rozwiązywania problemów, która polega na podzieleniu złożonego problemu na mniejsze, łatwiejsze w zarządzaniu części, rozwiązywaniu każdej części indywidualnie, a następnie łączeniu rozwiązań w celu rozwiązania pierwotnego problemu. Jest to szeroko stosowana technika algorytmiczna w informatyce i matematyce.

Przykład: w Sortowanie przez scalanie algorytm, Dziel i rządź strategia służy do sortowania listy elementów. Poniższy obrazek ilustruje stany dzielenia i łączenia w celu sortowania tablicy za pomocą Sortowanie przez scalanie .

Spis treści

• Co to jest Dziel i rządź?
• Etapy dziel i rządź
• Zastosowania metody „Dziel i rządź”.
• Podstawy dziel i zwyciężaj
• Standardowe algorytmy dziel i zwyciężaj
• Problemy oparte na wyszukiwaniu binarnym
• Ćwicz problemy z Dziel i rządź

Co to jest algorytm „Dziel i zwyciężaj”?

Dziel i zwyciężaj to technika rozwiązywania problemów, która polega na podzieleniu większego problemu na podproblemy, niezależnym rozwiązywaniu podproblemów i łączeniu rozwiązań tych podproblemów w celu uzyskania rozwiązania większego problemu.

Etapy algorytmu „Dziel i rządź”:

Algorytm Dziel i Rządź można podzielić na trzy etapy: Dzielić , Podbić I Łączyć .

1. Podziel:

• Podziel pierwotny problem na mniejsze podproblemy.
• Każdy podproblem powinien reprezentować część problemu ogólnego.
• Celem jest podzielenie problemu tak, aby dalszy podział nie był już możliwy.

2. Podbij:

• Rozwiązuj każdy z mniejszych podproblemów indywidualnie.
• Jeśli podproblem jest wystarczająco mały (często nazywany przypadkiem podstawowym), rozwiązujemy go bezpośrednio, bez dalszej rekurencji.
• Celem jest samodzielne znalezienie rozwiązań tych podproblemów.

3. Połącz:

• Połącz podproblemy, aby uzyskać ostateczne rozwiązanie całego problemu.
• Po rozwiązaniu mniejszych podproblemów rekurencyjnie łączymy ich rozwiązania, aby uzyskać rozwiązanie większego problemu.
• Celem jest sformułowanie rozwiązania pierwotnego problemu poprzez połączenie wyników podproblemów.

Zastosowania algorytmu „Dziel i rządź”:

• Sortowanie przez scalanie: Sortowanie przez scalanie jest klasycznym przykładem algorytmu sortowania typu „dziel i zwyciężaj”. Dzieli tablicę na mniejsze podtablice, sortuje je indywidualnie, a następnie łączy w celu uzyskania posortowanej tablicy.
• Mediana wyniku: Medianę zbioru liczb można znaleźć, stosując metodę dziel i zwyciężaj. Dzieląc rekurencyjnie zbiór na mniejsze podzbiory, można skutecznie wyznaczyć medianę.
• Wynik Min i Max: Algorytmu dziel i zwyciężaj można używać do jednoczesnego znajdowania elementów minimalnych i maksymalnych w tablicy. Dzieląc tablicę na połowy i porównując pary min-max z każdej połowy, można określić ogólną wartość minimalną i maksymalną w logarytmicznej złożoności czasowej.
• Mnożenie macierzy: Algorytm Strassena do mnożenia macierzy to technika dziel i zwyciężaj, która zmniejsza liczbę mnożeń wymaganych w przypadku dużych macierzy poprzez rozbicie macierzy na mniejsze podmacierze i połączenie ich iloczynów.
• Problem najbliższej pary: Problem najbliższej pary polega na znalezieniu dwóch najbliższych punktów w zbiorze punktów w przestrzeni wielowymiarowej. Algorytm dziel i zwyciężaj, taki jak algorytm dziel i zwyciężaj najbliższej pary, może skutecznie rozwiązać ten problem poprzez rekurencyjny podział punktów i łączenie rozwiązań podproblemów.

Podstawy algorytmu „Dziel i rządź”:

• Wprowadzenie do Dziel i rządź
• Programowanie dynamiczne a metoda „dziel i zwyciężaj”.
• Zmniejszaj i zwyciężaj
• Zaawansowane twierdzenie główne o powtarzalności dziel i zwyciężaj

Standardowe algorytmy włączone Algorytm dziel i zwyciężaj :

• Wyszukiwanie binarne
• Sortowanie przez scalanie
• Szybkie sortowanie
• Oblicz pow(x, n)
• Algorytm Karatsuby do szybkiego mnożenia
• Mnożenie macierzy Strassena
• Wypukły kadłub (prosty algorytm dziel i zwyciężaj)
• Algorytm Quickhulla dla wypukłego kadłuba

Problemy związane z wyszukiwaniem binarnym:

• Znajdź element szczytowy w danej tablicy
• Sprawdź element większościowy w posortowanej tablicy
• K-ty element dwóch posortowanych tablic
• Znajdź liczbę zer
• Znajdź liczbę rotacji w tablicy posortowanej z obróceniem
• Znajdź punkt, w którym monotonicznie rosnąca funkcja staje się dodatnia za pierwszym razem
• Mediana dwóch posortowanych tablic
• Mediana dwóch posortowanych tablic o różnych rozmiarach
• Problem partycji malarza przy użyciu wyszukiwania binarnego

Ćwicz problemy na Algorytm dziel i zwyciężaj :

• Pierwiastek kwadratowy z liczby całkowitej
• Maksimum i minimum tablicy przy użyciu minimalnej liczby porównań
• Znajdź częstotliwość każdego elementu w tablicy o ograniczonym zakresie w czasie krótszym niż O(n).
• Problem z kafelkowaniem
• Licz inwersje
• Problem Skyline'a
• Wyszukiwanie w tablicy 2D posortowanej wierszowo i kolumnowo
• Przydziel minimalną liczbę stron
• Potęgowanie modułowe (potęga w arytmetyce modułowej)

Szybkie linki :

• Naucz się struktury danych i algorytmów | Poradnik DSA
• „Rozwiązywanie problemów” w dziele i rządzeniu
• „Quizzy” na temat „Dziel i rządź”.