logo

TechCodeview

Algoritmus rozděl a panuj

Algoritmus rozděl a panuj je strategie řešení problémů, která zahrnuje rozčlenění složitého problému na menší, lépe zvládnutelné části, řešení každé části jednotlivě a následnou kombinaci řešení k vyřešení původního problému. Je to široce používaná algoritmická technika v informatice a matematice.

Příklad: V Sloučit třídění algoritmus, Rozděl a panuj strategie se používá k třídění seznamu prvků. Níže uvedený obrázek ilustruje stavy dělení a slučování, pomocí kterých lze pole třídit Sloučit třídění .



Obsah

Co je algoritmus rozděl a panuj?

Divide and Conquer je technika řešení problémů, která zahrnuje rozdělení většího problému na dílčí problémy, samostatné řešení dílčích problémů a kombinování řešení těchto dílčích problémů, aby se dosáhlo řešení většího problému.



Fáze algoritmu rozděl a panuj:

Algoritmus rozděl a panuj lze rozdělit do tří fází: Rozdělit , Dobýt a Spojit .

1. Rozdělit:

  • Rozdělte původní problém na menší dílčí problémy.
  • Každý dílčí problém by měl představovat část celkového problému.
  • Cílem je rozdělit problém tak dlouho, dokud nebude možné další rozdělení.

2. Dobýt:

  • Vyřešte každý z menších dílčích problémů samostatně.
  • Pokud je podproblém dostatečně malý (často označovaný jako základní případ), řešíme jej přímo bez další rekurze.
  • Cílem je najít řešení pro tyto dílčí problémy nezávisle.

3. Sloučit:

  • Spojením dílčích problémů získáte konečné řešení celého problému.
  • Jakmile jsou menší dílčí problémy vyřešeny, rekurzivně kombinujeme jejich řešení, abychom získali řešení většího problému.
  • Cílem je formulovat řešení původního problému sloučením výsledků z dílčích problémů.

Aplikace algoritmu rozděl a panuj:

  • Sloučit třídění: Merge sort je klasickým příkladem třídícího algoritmu rozděl a panuj. Rozdělí pole na menší podpole, seřadí je jednotlivě a poté je sloučí, aby se získalo setříděné pole.
  • Medián nálezu: Medián množiny čísel lze nalézt pomocí přístupu rozděl a panuj. Rekurzivním rozdělením souboru na menší podmnožiny lze efektivně určit medián.
  • Zjištění min a max: Algoritmus Divide and Conquer lze použít k současnému nalezení minimálních i maximálních prvků v poli. Rozdělením pole na poloviny a porovnáním min-max párů z každé poloviny lze celkové min a max identifikovat v logaritmické časové složitosti.
  • Násobení matice: Strassenův algoritmus pro násobení matic je technika rozděl a panuj, která snižuje počet násobení potřebných pro velké matice tím, že matice rozděluje na menší podmatice a kombinuje jejich produkty.
  • Problém s nejbližším párem: Problém nejbližšího páru zahrnuje nalezení dvou nejbližších bodů v množině bodů ve vícerozměrném prostoru. Algoritmus rozděl a panuj, jako je algoritmus nejbližšího páru rozděl a panuj, může tento problém efektivně vyřešit rekurzivním dělením bodů a slučováním řešení z dílčích problémů.

Základy algoritmu rozděl a panuj:

Standardní algoritmy zapnuty Algoritmus rozděl a panuj :

Problémy založené na binárním vyhledávání:

  • Najděte vrcholový prvek v daném poli
  • Zkontrolujte majoritní prvek v seřazeném poli
  • K-tý prvek dvou tříděných polí
  • Najděte počet nul
  • Najděte počet otočení v poli Rotated Sorted
  • Najděte bod, kdy se monotónně rostoucí funkce poprvé stane kladnou
  • Medián dvou seřazených polí
  • Medián dvou seřazených polí různých velikostí
  • Problém s oddílem malíře pomocí binárního vyhledávání

Procvičte si problémy Algoritmus rozděl a panuj :

  • Druhá odmocnina z celého čísla
  • Maximum a minimum pole pomocí minimálního počtu porovnání
  • Najděte frekvenci každého prvku v poli omezeného rozsahu za méně než O(n) čas
  • Problém s obklady
  • Počítat inverze
  • Problém Skyline
  • Hledejte v 2D poli uspořádaném po řádcích a sloupcích
  • Přidělte minimální počet stránek
  • Modulární umocňování (výkon v modulární aritmetice)

Rychlé odkazy :

  • Naučte se datovou strukturu a algoritmy | Výukový program DSA
  • „Procvičování problémů“ o rozdělování a panování
  • „Kvízy“ na téma Rozděl a panuj