Dziel i rządź Algorytm to technika rozwiązywania problemów stosowana do rozwiązywania problemów poprzez podzielenie głównego problemu na podproblemy, rozwiązywanie ich indywidualnie, a następnie łączenie ich w celu znalezienia rozwiązania pierwotnego problemu. W tym artykule omówimy, w jaki sposób algorytm „dziel i zwyciężaj” jest pomocny i jak możemy go wykorzystać do rozwiązywania problemów.

Spis treści

• Dziel i rządź – definicja algorytmu
• Działanie algorytmu „Dziel i zwyciężaj”.
• Charakterystyka algorytmu „Dziel i rządź”.
• Przykłady algorytmu „Dziel i rządź”.
• Analiza złożoności algorytmu dziel i zwyciężaj
• Zastosowania algorytmu „Dziel i rządź”.
• Zalety algorytmu „Dziel i zwyciężaj”.
• Wady algorytmu „Dziel i rządź”.

Dziel i rządź Definicja algorytmu:

Algorytm dziel i zwyciężaj polega na podzieleniu większego problemu na mniejsze podproblemy, rozwiązywaniu ich niezależnie, a następnie łączeniu ich rozwiązań w celu rozwiązania pierwotnego problemu. Podstawową ideą jest rekurencyjne dzielenie problemu na mniejsze podproblemy, dopóki nie staną się wystarczająco proste, aby można je było bezpośrednio rozwiązać. Po uzyskaniu rozwiązań podproblemów łączy się je w celu uzyskania rozwiązania ogólnego.

Działanie algorytmu „Dziel i rządź”:

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

Python drukuje z dokładnością do 2 miejsc po przecinku

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.

Charakterystyka algorytmu „Dziel i rządź”:

Algorytm „dziel i rządź” polega na podzieleniu 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. Charakterystyka algorytmu „Dziel i rządź” jest następująca:

• Podział problemu : Pierwszym krokiem jest podzielenie problemu na mniejsze, łatwiejsze do rozwiązania podproblemy. Podziału tego można dokonać rekurencyjnie, dopóki podproblemy nie staną się wystarczająco proste do bezpośredniego rozwiązania.
• Niezależność podproblemów : Każdy podproblem powinien być niezależny od pozostałych, co oznacza, że ​​rozwiązanie jednego podproblemu nie zależy od rozwiązania innego. Pozwala to na równoległe przetwarzanie lub równoczesną realizację podproblemów, co może prowadzić do wzrostu wydajności.
• Pokonanie każdego podproblemu : Po podzieleniu podproblemy są rozwiązywane indywidualnie. Może to obejmować rekurencyjne stosowanie tego samego podejścia „dziel i zwyciężaj”, aż podproblemy staną się wystarczająco proste do bezpośredniego rozwiązania, lub może wymagać zastosowania innego algorytmu lub techniki.
• Łączenie rozwiązań : Po rozwiązaniu podproblemów ich rozwiązania są łączone w celu uzyskania rozwiązania pierwotnego problemu. Ten etap łączenia powinien być stosunkowo skuteczny i prosty, ponieważ rozwiązania podproblemów powinny być zaprojektowane tak, aby płynnie do siebie pasowały.

Przykłady algorytmu „Dziel i rządź”:

1. Znalezienie elementu maksymalnego w tablicy:

Możemy użyć algorytmu dziel i zwyciężaj, aby znaleźć maksymalny element tablicy, dzieląc tablicę na dwie podtablice o jednakowych rozmiarach i znajdując maksimum tych dwóch pojedynczych połówek, ponownie dzieląc je na dwie mniejsze połówki. Dzieje się tak aż do osiągnięcia podtablic o rozmiarze 1. Po dotarciu do elementów zwracamy element maksymalny i łączymy podtablice, zwracając maksimum w każdej podtablicy.

// function to find the maximum no. // in a given array. int findMax(int a[], int lo, int hi) {  // If lo becomes greater than hi, then return minimum  // integer possible  if (lo>cześć) zwróć INT_MIN;  // Jeśli podtablica ma tylko jeden element, zwróć // element if (lo == hi) return a[lo];  int mid = (lo + hi) / 2;  // Pobierz maksymalny element z lewej połowy int leftMax = findMax(a, lo, mid);  // Pobierz maksymalny element z prawej połowy int RightMax = findMax(a, mid + 1, hi);  // Zwraca maksymalny element z lewej i prawej strony // połowa return max(leftMax, RightMax); }>

// Function to find the maximum number // in a given array. static int findMax(int[] a, int lo, int hi) {  // If lo becomes greater than hi, then return  // minimum integer possible  if (lo>cześć) zwróć liczbę całkowitą.MIN_VALUE;  // Jeśli podtablica ma tylko jeden element, zwróć // element if (lo == hi) return a[lo];  int mid = (lo + hi) / 2;  // Pobierz maksymalny element z lewej połowy int leftMax = findMax(a, lo, mid);  // Pobierz maksymalny element z prawej połowy int RightMax = findMax(a, mid + 1, hi);  // Zwraca maksymalny element z lewej i // prawej połowy return Math.max(leftMax, RightMax); }>

# Function to find the maximum number # in a given array. def find_max(a, lo, hi): # If lo becomes greater than hi, then return minimum # integer possible if lo>hi: return float('-inf') # Jeśli podtablica ma tylko jeden element, zwróć # element if lo == hi: return a[lo] mid = (lo + hi) // 2 # Uzyskaj maksimum element z lewej połowy left_max = find_max(a, lo, mid) # Znajdź maksymalny element z prawej połowy Right_max = find_max(a, mid + 1, hi) # Zwróć maksymalny element z lewej i prawej strony # połowa return max (lewy_maks., prawy_maks.)>

// Function to find the maximum number // in a given array. static int FindMax(int[] a, int lo, int hi) {  // If lo becomes greater than hi, then return  // minimum integer possible  if (lo>cześć) zwróć int.MinValue;  // Jeśli podtablica ma tylko jeden element, zwróć // element if (lo == hi) return a[lo];  int mid = (lo + hi) / 2;  // Pobierz maksymalny element z lewej połowy int leftMax = FindMax(a, lo, mid);  // Pobierz maksymalny element z prawej połowy int RightMax = FindMax(a, mid + 1, hi);  // Zwraca maksymalny element z lewej i // prawej połowy return Math.Max(leftMax, RightMax); }>

// Function to find the maximum number // in a given array. function findMax(a, lo, hi) {  // If lo becomes greater than hi, then return minimum  // integer possible  if (lo>cześć) zwróć numer.MIN_VALUE;  // Jeśli podtablica ma tylko jeden element, zwróć // element if (lo === hi) return a[lo];  const mid = Math.floor((lo + hi) / 2);  // Pobierz maksymalny element z lewej połowy const leftMax = findMax(a, lo, mid);  // Pobierz maksymalny element z prawej połowy const RightMax = findMax(a, mid + 1, hi);  // Zwraca maksymalny element z lewej i prawej strony // połowa zwraca Math.max(leftMax, RightMax); }>

2. Znalezienie minimalnego elementu tablicy:

Podobnie możemy użyć algorytmu dziel i zwyciężaj, aby znaleźć minimalny element tablicy, dzieląc tablicę na dwie podtablice o jednakowych rozmiarach i znajdując minimum tych dwóch pojedynczych połówek, ponownie dzieląc je na dwie mniejsze połówki. Dzieje się tak aż do osiągnięcia podtablic o rozmiarze 1. Po dotarciu do elementów zwracamy element minimalny i łączymy podtablice, zwracając minimum w każdej podtablicy.

int na ciąg znaków w Javie

3. Sortowanie przez scalanie:

Możemy użyć algorytmu dziel i zwyciężaj, aby posortować tablicę w kolejności rosnącej lub malejącej, dzieląc tablicę na mniejsze podtablice, sortując mniejsze podtablice, a następnie łącząc posortowane tablice w celu posortowania oryginalnej tablicy.

Analiza złożoności algorytmu dziel i zwyciężaj:

T(n) = aT(n/b) + f(n), gdzie n = rozmiar danych wejściowych a = liczba podproblemów w rekurencji n/b = rozmiar każdego podproblemu. Zakłada się, że wszystkie podproblemy mają ten sam rozmiar. f(n) = koszt pracy wykonanej poza wywołaniem rekurencyjnym, który obejmuje koszt podziału problemu i koszt połączenia rozwiązań

Zastosowania algorytmu „Dziel i rządź”:

Poniżej przedstawiono kilka standardowych algorytmów zgodnych z algorytmem Dziel i rządź:

• Szybkie sortowanie to algorytm sortowania, który wybiera element przestawny i przestawia elementy tablicy w taki sposób, że wszystkie elementy mniejsze niż wybrany element przestawny przesuwają się na lewą stronę elementu przestawnego, a wszystkie większe elementy na prawą stronę. Na koniec algorytm rekurencyjnie sortuje podtablice po lewej i prawej stronie elementu obrotowego.
• Sortowanie przez scalanie jest również algorytmem sortującym. Algorytm dzieli tablicę na dwie połowy, sortuje je rekurencyjnie i na koniec łączy obie posortowane połowy.
• 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żna rozwiązać w czasie O(n^2), obliczając odległości każdej pary punktów i porównując odległości w celu znalezienia minimum. Algorytm Dziel i rządź rozwiązuje problem w czasie O(N log N).
• 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 wynosi O(n^3). Algorytm Strassena mnoży dwie macierze w czasie O(n^2,8974).
• Algorytm szybkiej transformaty Fouriera Cooleya – Tukeya (FFT). jest najpopularniejszym algorytmem FFT. Jest to algorytm dziel i zwyciężaj, który działa w czasie O(N log N).
• Algorytm Karatsuby do szybkiego mnożenia wykonuje mnożenie dwóch ciągów binarnych w O(n^1,59) gdzie n jest długością ciągu binarnego.

Zalety algorytmu „Dziel i rządź”:

• Rozwiązywanie trudnych problemów: Technika „dziel i rządź” jest narzędziem służącym do koncepcyjnego rozwiązywania trudnych problemów. np. Zagadka Wieża Hanoi. Wymaga sposobu podzielenia problemu na podproblemy i rozwiązania ich wszystkich jako indywidualnych przypadków, a następnie połączenia podproblemów w pierwotny problem.
• Wydajność algorytmu: Algorytm dziel i zwyciężaj często pomaga w odkrywaniu wydajnych algorytmów. Jest to klucz do algorytmów takich jak szybkie sortowanie i sortowanie przez scalanie oraz szybkie transformaty Fouriera.
• Równoległość: Zwykle algorytmy Dziel i Rządź są używane w maszynach wieloprocesorowych wyposażonych w systemy pamięci współdzielonej, w których nie trzeba wcześniej planować przesyłania danych między procesorami, ponieważ różne podproblemy mogą być wykonywane na różnych procesorach.
• Dostęp do pamięci: Algorytmy te w naturalny sposób efektywnie wykorzystują pamięci podręczne. Ponieważ podproblemy są na tyle małe, że można je rozwiązać w pamięci podręcznej bez użycia wolniejszej pamięci głównej. Każdy algorytm efektywnie wykorzystujący pamięć podręczną nazywany jest pamięcią podręczną.

Wady algorytmu „Dziel i rządź”:

• Nad głową: Proces dzielenia problemu na podproblemy, a następnie łączenia rozwiązań może wymagać dodatkowego czasu i zasobów. Ten narzut może być znaczący w przypadku problemów, które są już stosunkowo małe lub mają proste rozwiązanie.
• Złożoność: Podzielenie problemu na mniejsze podproblemy może zwiększyć złożoność ogólnego rozwiązania. Jest to szczególnie prawdziwe, gdy podproblemy są współzależne i muszą być rozwiązywane w określonej kolejności.
• Trudność wdrożenia: Niektóre problemy trudno podzielić na mniejsze podproblemy lub wymagają do tego złożonego algorytmu. W takich przypadkach wdrożenie rozwiązania opartego na zasadzie „dziel i zwyciężaj” może być trudne.
• Ograniczenia pamięci: Podczas pracy z dużymi zbiorami danych, wymagania dotyczące pamięci do przechowywania pośrednich wyników podproblemów mogą stać się czynnikiem ograniczającym.

Często zadawane pytania (FAQ) dotyczące algorytmu „Dziel i zwyciężaj”:

1. Czym jest algorytm Dziel i Rządź?

Dziel i zwyciężaj to technika rozwiązywania problemów, w której problem jest dzielony na mniejsze, łatwiejsze do rozwiązania podproblemy. Podproblemy te są rozwiązywane rekurencyjnie, a następnie ich rozwiązania są łączone w celu rozwiązania pierwotnego problemu.

2. Jakie są kluczowe etapy algorytmu „Dziel i rządź”?

Główne kroki to:

Dzielić : Podziel problem na mniejsze podproblemy.

Podbić : Rozwiąż podproblemy rekurencyjnie.

Łączyć : Połącz lub połącz rozwiązania podproblemów, aby uzyskać rozwiązanie pierwotnego problemu.

3. Jakie są przykłady problemów rozwiązanych przy użyciu metody Dziel i rządź?

Algorytm „Dziel i zwyciężaj” jest używany w algorytmach sortowania, takich jak sortowanie przez scalanie i sortowanie szybkie, znajdowanie najbliższej pary punktów, algorytm Strassena itp.

4. W jaki sposób sortowanie przez scalanie wykorzystuje podejście „Dziel i rządź”?

Sortowanie przez scalanie dzieli tablicę na dwie połowy, rekursywnie sortuje każdą połowę, a następnie łączy posortowane połówki, aby utworzyć ostateczną posortowaną tablicę.

programowanie w tablicach C

5. Jaka jest złożoność czasowa algorytmów Dziel i Rządź?

Złożoność czasowa różni się w zależności od konkretnego problemu i sposobu jego wdrożenia. Ogólnie rzecz biorąc, wiele algorytmów Dziel i rządź ma złożoność czasową O(n log n) lub lepszą.

6. Czy algorytmy Dziel i Rządź można zrównoleglić?

Tak, algorytmy Dziel i Rządź często w naturalny sposób można zrównoleglić, ponieważ niezależne podproblemy można rozwiązywać jednocześnie. Dzięki temu nadają się do równoległych środowisk obliczeniowych.

7. Jakie są strategie wyboru przypadku bazowego w algorytmach Dziel i Rządź?

Przypadek podstawowy powinien być na tyle prosty, że można go rozwiązać bezpośrednio, bez dalszego podziału. Często jest wybierany na podstawie najmniejszego rozmiaru danych wejściowych, w przypadku którego problem można rozwiązać w trywialny sposób.

8. Czy są jakieś wady lub ograniczenia w korzystaniu z funkcji Dziel i rządź?

Choć metoda „Dziel i rządź” może prowadzić do skutecznych rozwiązań wielu problemów, może nie być odpowiednia w przypadku wszystkich typów problemów. Koszty ogólne wynikające z rekurencji i łączenia rozwiązań mogą również stanowić problem w przypadku problemów o bardzo dużych rozmiarach.

9. Jak analizujesz złożoność przestrzenną algorytmów Dziel i Rządź?

Złożoność przestrzeni zależy od czynników takich jak głębokość rekurencji i przestrzeń pomocnicza wymagana do łączenia rozwiązań. Analiza złożoności przestrzeni zazwyczaj obejmuje rozważenie przestrzeni wykorzystywanej przez każde wywołanie rekurencyjne.

10. Jakie są typowe zalety algorytmu „Dziel i rządź”?

Algorytm Dziel i Rządź ma wiele zalet. Niektóre z nich obejmują:

• Rozwiązywanie trudnych problemów
• Wydajność algorytmu
• Równoległość
• Dostęp do pamięci

Dziel i zwyciężaj to popularna technika algorytmiczna w informatyce, która polega na dzieleniu problemu na mniejsze podproblemy, rozwiązywaniu każdego podproblemu niezależnie, a następnie łączeniu rozwiązań podproblemów w celu rozwiązania pierwotnego problemu. Podstawową ideą tej techniki jest podzielenie problemu na mniejsze, łatwiejsze do opanowania podproblemy, które można łatwiej rozwiązać.