Jämförelse av olika metoder att konstruera algoritmer

1. Backtracking
   Används för problem där det krävs en stor mängd beslut och där alla beslut måste vara riktiga för att målet ska nås. Ett typiskt exempel på problem är att hitta rätt väg genom en labyrint. Denna metod ger väsentligt snabbare algoritmer än att prova alla möjliga kombinationer av beslut. Det finns däremot ingen garanti för att den bästa lösningen  (tex den kortaste vägen genom labyrinten) hittas.
2. Glupska algoritmer
   Denna typ av algoritmer blir mycket snabba och är lätta att konstruera men det finns ingen garanti för att de kan lösa problemet eller för att den lösning de eventuellt hittar är den bästa. Det är ofta svårt att bevisa att de fungerar korrekt.
3. Söndra och härska
   Är mer generell än backtracking och det är lättare att bevisa att denna typ av algoritmer fungerar än det är med glupska algoritmer. Med andra ord en användbar metod. Det är dock inte säkert att den ger en prestandavinst (även om så ofta är fallet). En förutsättning för att algoritmen ska vara användbar är att problemet kan delas upp i oberoende delproblem. Om så inte är fallet kan denna metod kombineras med dynamisk programmering.
4. Dynamisk programmering
   Alltid användbar om samma arbete utförs i olika rekursiva anrop. Ger ofta betydande prestandaförbättring genom att eleminera onödigt arbete. Kan ge en mindre prestandaförbättring även om inte samma arbete utförs flera gånger. Detta åstadkoms i så fall genom att byta rekursion mot iteration och genom att förenkla varje beräkning. O(T(n)) förändras dock inte i detta fall.

5. Färdiga väl beprövade algoritmer
   Många problem (till exempel sortering) är så vanligt förekommmande att det redan finns ett flertal genomanalyserade algoritmer som löser dem. I sådana fall är det bättre att välja en sådan i stället för att försöka hitta på en egen algoritm.
6. Egenkonstruerade klurigheter som inte tillhör någon av kategorierna 1 - 4.
   Det är väldigt lätt att överskatta denna metod. Algoritmer vi konstruerar själva är ofta inte så generella som det kan tyckas. Det är inte alltid helt lätt att bevisa att en algoritm alltid fungerar eller att den ger den bästa lösningen. Det är bättre att ta del av datalogins samlade erfarenheter än att klura själv. Vidare är det främsta rådet angående att optimera sin kod att inte göra det i onödan. Det är alltid bäst att skriva välstrukturerad och lättunderhållen kod först och att sedan optimera den vid behov. Innan den optimeras måste vi ta reda på exakt vad i koden som tar för lång tid.
7. Råräkning
   Om ingen annan lösning finns återstår bara att (ofta med hjälp av nästlade loopar) gå igenom alla möjliga kombinationer tills vi hittar en bra (eller den bästa) lösning. Problemet är att algoritmer av denna typ ofta blir oanvändbart långsamma. Det finns anledning till tveksamhet om O(T(n)) >= n².

Hur välja en metod?

1. Om det finns en lämplig algoritm av typ fem, ta den.
2. Om det är viktigt med en väldigt snabb eller väldigt lättkonstruerad algoritm, ta typ två. Var dock beredd på att det kan vara svårt att försäkra sig om att den alltid fungerar.
3. Välj kategori ett om problemet kräver att en stor mängd korrekta beslut fattas.
4. Prova med metod tre. Om det inte går får det bli metod sju. Försök, oavsett vilken av dem det blir, att förbättra algoritmen med hjälp av metod fyra.
5. Om det fortfarande inte fungerar återstår bara metod sex.