Söndra och härska (divide and conquer)

Detta är en mycket vanlig metod att konstruera algoritmer. Den leder oftast till snabba algoritmer.

Definition (informell)

Algoritmer konstruerade emligt denna metod består av två delar:

Söndra: Problemet delas upp i mindre och mindre delproblem, helst ända tills delproblemen är triviala att lösa.
Härska: Lösningen på det ursprungliga problemet ges genom att kombinera lösningarna på delproblemen.

För att en funktion ska vara en implementation av söndra och härska måste den innehålla minst två rekursiva anrop som löser olika delproblem.

Ett typiskt exempel

Här kommer ett typiskt exempel på hur ett problem löses med tekniken söndra och härska. Problemet är att i en sekvens med heltal hitta den delsekvens vars heltal ger störst summa, se sid 164 i kompendiet.

En typisk lösning finns på sid 165. Den går ut på att låta ett undre index, l, stega igenom alla element i sekvensen. För varje l låter vi ett övre index, h, stega igenom alla högre index och samtidigt beräkna alla delsekvensers summor. Eftersom den består av två nästlade loopar är storleksordningen av dess komplexitetsfunktion O(n²). Det är knappast acceptabelt men snabbare går det inte att hitta en lösning om alla möjliga delsekvensers summor ska beräknas.

Vi ska nu se hur problemet kan lösas snabbare med hjälp av söndra och härska (denna lösning finns på sid 167). Först ska det delas upp i mindre delproblem (söndra). Detta görs genom att dela sekvensen i två halvor. Den sökta delsekvensen kan nu finnas på tre olika ställen:

I den ena halvan
I den andra halvan
Den börjar i den ena halvan och slutar i den andra.

När vi känner de största summorna i dessa tre fall kan vi enkelt jämföra dem och få fram den största (härska). Jämförelsen är oberoende av n, dvs O(1). Men för att denna algoritm ska vara bättre än den föregående måste de tre delmomenten också vara snabbare än O(n²).

Vi betraktar först fall tre. Här går det att undvika nästlade loopar eftersom en sekvens som börjar i den ena halvan och slutar i den andra måste innehålla både det översta elemntet i den nedre sekvensen och det nedersta elementet i den övre sekvensen. Vi tar fram den största delsumman i den undre halvan genom att loopa från det översta elemntet i den nedre sekvensen och nedåt och beräkna alla delsummor. Sedan loopar vi på samma sätt genom den övre delsekvensen. Genom att summera dessa båda delsummor får vi den största summan som börjar i den ena halvan och slutar i den andra. Denna lösning består av två loopar som inte är nästlade, dess komplexitetsfunktion är alltså av storleksordningen O(2n) = O(n).

Nu gäller det att hitta lösningar på fall ett och två. Det görs genom att fortsätta att dela upp dem i halvor och göra rekursiva anrop ända tills vi får delsekvenser som bara består av ett element. Den största summan i dessa minimala sekvenser är naturligtvis värdet av det enda elementet (eller 0 om elementet är negativt). Här är ett program med denna lösning, DivideAndConquer.c .

Analys av exekveringshastighet

Låt oss nu beräkna komplexitetsfunktionen, T(n), för denna lösning. Om n=1 returneras svaret direkt eftersom det är basfallet, alltså är T(1) = 1. Om n>1 löses tre delproblem, fall ett, två och tre ovan. I fall tre är O(T(n)) = O(n) enligt ovan. Fall ett och två leder till två ytterligare exekveringar ev funktionen, men nu med n/2 element. Detta innebär att T(n) = 2T(n/2) + O(n). För att förenkla beräkningarna antar vi att n är en jämn tvåpotens och ersätter dessutom O(n) med n. Detta kommer inte att påverka O(T(n)). Vi har alltså T(n) = 2T(n/2) + n och T(1) = 1.

Nu gäller det lösa ut T(n) ur denna funktion. Vi börjar med att dividera båda leden med n: T(n)/n = T(n/2)/(n/2) + 1.
Detta gäller för alla n som är tvåpotenser. Alltså gäller alla dessa ekvationer:
T(n)/n = T(n/2)/(n/2) + 1
T(n/2)/(n/2) = T(n/4)/(n/4) + 1
T(n/4)/(n/4) = T(n/8)/(n/8) + 1
...
T(2)/2 = T(1)/1 + 1
Nu summerar vi dessa ekvationer. Det visar sig då att de flesta termerna (tex T(n/2)/(n/2)) finns på båda sidor och alltså kan strykas. Efter att ha strukit alla dessa termer återstår T(n)/n = T(1)/1 + log₂ n. log₂ n är summan av alla 1:orna eftersom det finns log₂ n ekvationer. T(1) = 1 => T(n) = n + nlog n. Detta innebär att O(T(n)) = nlog n eftersom nlog n växer snabbare än n när n växer.

Detta var ett typiskt exempel på hur exekveringshastigheten med hjälp av tekniken söndra och härska kunde ökas från O(n²) till O(nlog n).

Vi har nu sett att om ett problem delas i två delproblem av halva storleken som löses rekursivt och om det tar O(n) tid att exekvera funktionen en gång så blir exekveringshastigheten O(nlog n). Men vad händer om vi delar upp problemet i tre delproblem av halva storleken? Eller om vi delar det i sju delproblem som har storleken en tredjedel och det tar O(n²) tid att exekvera funktionen en gång? Här kommer en generell formel för exekekveringstiden. Beviset liknar det ovan med vi tar inte upp det här.
A är antalet delproblem, A >= 1.
B är storleken av delproblemen, om tex delproblemen är hälften så stora som det ursprungliga problemet är B = 2. B > 1.
k anger att det tar O(n^k) tid att exekvera funktionen en gång.
Då gäller att O(T(n)), där T(n) = AT(n/B) + O(n^k ), är:
O(n^log_BA) om A > B^k
O(n^klog_B n) om A = B^k
O(n^k) om A < B^k

Vad innebär detta egentligen? I problemet med delsekvensens summa var A = 2, B = 2 och k = 1. Detta innebär att fall två ovan gäller och att O(T(n)) är n logn som vi redan sett. Om vi i stället varit tvugna att dela problemet i tre halvstora delproblem hade fall ett gällt och O(T(n)) hade varit n^log₂3 = n^1,59. Det betyder att tiden för att exekvera funktionen en gång (termen O(n^k)) saknar betydelse i detta fall så länge k < 1,59. Faktiskt finns k inte heller med i uttrycket för O(T(n)). Om däremot k hade varit större än 1,59 hade den termen tagit över och vi hade hamnat i fall tre där A och B saknar betydelse.

Avslutningsvis kan vi konstatera att O(T(n)) blir mindre i fall två och tre om k blir mindre. I fall ett är k redan så liten att O(n^k) saknar betydelse. Då finns det ingen anledning att minska k ytterligare. I fall ett och två kan exekveringstiden minskas genom att A minskas eller B ökas. I fall ett saknar k betydelse.

När ska söndra och härska användas?

För att denna metod ska passa måste problemet kunna delas upp i flera oberoende delproblem. Detta är långt ifrån alltid möjligt men om det lyckas kan vi vara säkra på att relativt snabbt nå en korrekt lösning. Detta eftersom vi följer den första andra och fjärde av rekursionens fyra regler:

Det måste finnas minst ett basfall.
Varje rekursion måste föra oss närmre ett basfall.
Lita på att rekursion fungerar.
Utför inte samma arbete flera gånger.

Fler exempel

Här kommer ytterligare några problem som löses med hjälp av söndra och härska.

Största värdet i en array (sid 161-162)

Här handlar det om att hitta det största värdet i en sekvens. En rättfram lösning vore att läsa igenom hela sekvensen och hela tiden komma ihåg det största värdet. Detta skulle ge en komplexitetsfunktion som vore O(n). Lösningen i kompendiet går i stället ut på att dela sekvensen i två halvor, rekursivt beräkna det största värdet i var och en av halvorna och sedan returnera det största av dessa värden. Rekursionens basfall är när sekvensen bara innehåller ett element. En analys av exekveringshastigheten ger att A = B = 2 (problemet delas i två oberoende halvor) och k = 0 (exekveringstiden för en instans av funktionen är oberoende av n). Detta innebär att fall 1 ovan gäller O(T(n)) = O(n^log_BA) = O(n). Vi vann alltså ingenting på att använda oss av tekniken söndra och härska. En närmare eftertanke (med hjälp av bilden på sid 162) avslöjar tvärtom den senare algoritmen kräver ungefär 2cn (där c är en konstant) instruktioner eftersom funktionen körs 2n gånger. Den rättframma lösningen kräver däremot bara cn instruktioner.

Exponentiering (sid 162-163)

Detta är inte söndra och härska i striktaste mening eftersom algoritmen bara innehåller ett rekursivt anrop. Formeln för exekveringshastigheten gäller dock och vi kan konstatera att A = 1, B = 2 och k = 0. Vi hamnar i fall två och O(T(n)) = O(log n).

Mergesort (sid 163 - 164)

En sekvens sorteras genom att den delas upp i två delsekvenser som sorteras var för sig genom rekursiva anrop. Därefter samsorteras de två delsekvenserna genom att vi hela tiden tar det minsta (i exemplet sorteras sekvensen i stigande ordning) av de första elementen i delsekvenserna. Basfallet är när sekvensen bara har ett eller två element, då dessa sorteras. A = B = 2 eftersom sekvensen delas i två halvor. k = 1 eftersom algoritmen innehåller tre loopar från 0 till n, två för att dela sekvensen i delsekvenser och en för att sortera ihop delsekvenserna igen. Detta ger (enligt fall två) O(T(n)) = O(nlog n).

Inom parantes kan nämnas att mergesort inte är fullt så bra som det verkar eftersom det dels tar lång tid att utföra all kopiering av sekvenserna och dels krävs mycket minne för alla delsekvenser.