Splitt og hersk-algoritme

En splitt og hersk-algoritme er et paradigme innenfor algoritmer som er basert på mangegreiners rekursjon. Den arbeider rekursivt ved å bryte ned et problem i to eller flere underproblemer av samme eller beslektet type, inntil disse blir enkel nok til å bli løst direkte. Løsningen på underproblemene blir kombinert for å gi løsningen på det opprinnelige problem.

Splitt og hersk-teknikken er grunnlaget for effektive algoritmer for alle typer problemer, slik som sorteringsalgoritmer (quicksort, flettesortering), multiplisering av store tall (Karatsubaalgoritmen), å finne de nærmeste par av punkter, syntaktisk analyse (toppen ned-parsere) og beregning av Discrete Fourier transform (FFT).

Denne artikkelen er en spire. Du kan hjelpe Wikipedia ved å utvide den.

Autoritetsdata