Opdel og erobre algoritme Betydning: Forklaret med eksempler

Hvad er opdelings- og erobringsalgoritmer? (Og nej, det er ikke "Divide and Concur")

Divide and Conquer er et algoritmisk paradigme (undertiden fejlagtigt kaldet "Divide and Concur" - et sjovt og passende navn), der ligner Grådig og dynamisk programmering. En typisk Divide and Conquer-algoritme løser et problem ved hjælp af følgende tre trin.

  1. Opdel : Opdel det givne problem i delproblemer af samme type. Dette trin indebærer at opdele problemet i mindre delproblemer. Underproblemer skal repræsentere en del af det oprindelige problem. Dette trin tager generelt en rekursiv tilgang til at opdele problemet, indtil intet underproblem kan deles yderligere. På dette stadium bliver underproblemer atomare, men repræsenterer stadig en del af det aktuelle problem.
  2. Erobrer : Løs rekursivt disse underproblemer. Dette trin modtager mange mindre delproblemer, der skal løses. Generelt betragtes problemerne på dette niveau som 'løst' alene.
  3. Kombiner : Kombiner svarene korrekt. Når de mindre delproblemer løses, kombinerer dette trin dem rekursivt, indtil de formulerer en løsning på det oprindelige problem. Denne algoritmiske tilgang fungerer rekursivt og erobre & flette trin fungerer så tæt, at de ser ud som en.

Denne metode giver os normalt mulighed for i høj grad at reducere tidskompleksiteten.

For eksempel bruger Bubble Sort en kompleksitet af O(n^2), mens quicksort (en applikation af Divide And Conquer) reducerer tidskompleksiteten til O(nlog(n)). Lineær søgning har tidskompleksitet O(n), mens binær søgning (en applikation af opdeling og erobring) reducerer tidskompleksiteten til O(log(n)).

Følgende er nogle standardalgoritmer, der er af Divide and Conquer-algoritmerne.

Binær søgning  er en søgningsalgoritme. I hvert trin sammenligner algoritmen inputelementet (x) med værdien af ​​det midterste element i array. Hvis værdierne stemmer overens, skal du returnere indekset for midten. Ellers, hvis x er mindre end det midterste element, gentager algoritmen sig til venstre side af det midterste element, ellers vender det tilbage til højre side af det midterste element.

Quicksort  er en sorteringsalgoritme. Algoritmen vælger et pivotelement, omarrangerer arrayelementerne på en sådan måde, at alle elementer, der er mindre end det valgte pivotelement, bevæger sig til venstre side af pivot, og alle større elementer bevæger sig til højre side. Endelig sorterer algoritmen rekursivt underarrangementer til venstre og højre for drejelementet.

Flet sortering  er også en sorteringsalgoritme. Algoritmen deler arrayet i to halvdele, sorterer dem rekursivt og fletter de to sorterede halvdele til sidst. Tidenes kompleksitet i denne algoritme er O(nLogn), hvad enten det er den bedste sag, gennemsnittet eller værste tilfælde. Det er tid kompleksitet let kan forstås fra recidiv svarer til: T(n) = 2T(n/2) + n.

Nærmeste parpunkter  Problemet er at finde det nærmeste par punkter i et sæt punkter i xy-plan. Problemet kan løses i O(n^2)tide ved at beregne afstande for hvert par punkter og sammenligne afstande for at finde minimum. Divide and Conquer algoritmen løser problemet i O(nLogn)tide.

Strassens algoritme  er en effektiv algoritme til at multiplicere to matricer. En enkel metode til at multiplicere to matricer har brug for 3 indlejrede løkker og er O(n^3). Strassens algoritme multiplicerer to matricer i O(n^2.8974)tide.

Cooley – Tukey Fast Fourier Transform (FFT) algoritme  er den mest almindelige algoritme for FFT. Det er en opdelings- og erobringsalgoritme, der fungerer i O(nlogn)tide.

Karatsuba-algoritmen  var den første multiplikationsalgoritme asymptotisk hurtigere end den kvadratiske "grundskole" -algoritme. Det reducerer multiplikationen af ​​to n-cifrede tal til højst til n ^ 1.585 (hvilket er en tilnærmelse af log på 3 i base 2) enkeltcifrede produkter. Det er derfor hurtigere end den klassiske algoritme, som kræver n ^ 2 encifrede produkter.

Divide and Conquer (D & C) vs Dynamic Programming (DP)

Begge paradigmer (D & C og DP) opdeler det givne problem i delproblemer og løser underproblemer. Hvordan vælger jeg en af ​​dem til et givet problem? Divide and Conquer skal bruges, når de samme delproblemer ikke evalueres mange gange. Ellers skal der bruges dynamisk programmering eller memoisering.

For eksempel er binær søgning en Divide and Conquer-algoritme, vi evaluerer aldrig de samme delproblemer igen. På den anden side bør dynamisk programmering foretrækkes til beregning af det niende Fibonacci-nummer.