Verdeel-en-heers-algoritme

In de informatica is verdeel en heers een algoritmeontwerpparadigma. Een verdeel-en-heers-algoritme splitst een probleem recursief op in twee of meer deelproblemen van hetzelfde of verwante type, totdat deze eenvoudig genoeg worden om direct op te lossen. De oplossingen voor de deelproblemen worden vervolgens gecombineerd om een oplossing voor het oorspronkelijke probleem te geven.

De verdeel-en-heers-techniek is de basis van efficiënte algoritmen voor veel problemen, zoals sorteren (bijv. quicksort en mergesort) en het berekenen van de discrete fouriertransformatie (FFT).

Het ontwerpen van efficiënte verdeel-en-heers-algoritmen kan lastig zijn. Net als bij wiskundige inductie is het vaak nodig om het probleem te veralgemenen om het vatbaar te maken voor een recursieve oplossing. De juistheid van een verdeel-en-heers-algoritme wordt meestal bewezen door wiskundige inductie. De rekenkosten ervan worden vaak bepaald door het oplossen van recurrente betrekkingen.