Inledning
Algoritmer finns som begrepp både inom datavetenskap och inom matematik. En förklaring på ordet algoritm brukar vara en mängd väldefinierade instruktioner som löser en specifik uppgift.
Begreppet algoritm uppstod som ett sätt att beskriva procedurer för att lösa matematiska problem. Alan Turing formaliserade begreppet runt 1936 och lade samtidigt också grunden till hela datavetenskapen.
Algoritmer, precis som program, kan vara korta eller långa, komplicerade eller enkla.
Vi ska i artikeln kort ta upp tre olika sorters algoritmer då de spelar en central roll i kursen Programmering 1 på gymnasienivå. Dessa tre är:
- Sökalgoritmer
- Sorteringsalgoritmer
- Rekursiva algoritmer
Flödesschema
Ett bra sätt att beskriva hur en algoritm fungerar är att rita ett sk. flödesschema.
Ett flödesschema är en grafisk presentation som använder specifika symboler för att beskriva logik och flöde i ett program. Ett exempel kan vara en "algoritm" för att laga en lampa.
Komplexitetsanalys
Komplexitet är något en programmerare bör ha koll på. Komplexiteten hos en algoritm kan vara avgörande när vi väljer mellan två algoritmer som löser samma problem. Oftast vill man ha "den bästa" algoritmen men vad menas med det?
Oftast när man diskuterar "den bästa" algoritmen för ett problem så menar man den mest effektiva. Det finns tre kriterier som man mäter effektivitet med när man gör en komplexitetsanalys:
- Snabbast. Den algoritm som löser uppgiften på kortast tid.
- Minst resurser. Den algoritm som löser problemet med minst resurser, t.ex. förbrukar minst minne under tiden algoritmen jobbar.
- Minst komplicerad. Den algoritm som är enklast att begripa och tolka koden av. Detta kriterium är inte direkt mätbart som övriga två.
De två första kriterierna, snabbast och minst resurser, är rätt enkla att mäta i praktiken genom att provköra algoritmen. De går också utifrån koden att analysera fram. Det tredje kriteriet är mer subjektivt bedömt och brukar bli mindre prioriterat än de övriga. Vi använder oss gärna av komplicerade och svåra algoritmer (som vi kanske inte till fullo begriper) bara de gör jobbet snabbt och resurssnålt.
Ordo
Ordo, eller "the big O". Används för att beskriva effektivitet, både snabbhet och resurser, för en algoritm. Det är ett matematiskt begrepp som mäter hur "tung" en algoritm (formel) är. Vi behöver ett exempel.
using System;
namespace Test
{
class Program
{
static void Main(string[] args)
{
int number = int.Parse(Console.ReadLine());
for (int i = 0; i < number; i++)
{
Console.WriteLine(i);
}
}
}
}
Denna "algoritm" skriver ut så många tal som du ber den att göra (positiva heltal). För att undersöka algoritmens effektivitet gällande snabbhet så kikar vi på hur algoritmen beror av input eller den mängd data som skickas in.
Indatan eller mängden data som skickas in brukar betecknas n. Matar vi in 10 så skrivs 10 rader ut. Matar vi in 100 så skrivs 100 rader ut, etc. Alltså matar vi in n så skriver algoritmen ut n rader. Alltså mängden instruktioner som görs är n * "instruktionerna som krävs för varje utskrift".
För snabbhet (oftast bara kallat komplexitet) presterar denna algoritm O(n).
För att analysera resurser så kan vi studera hur många eller om det skapas några variabler för att lösa problemet. Strikt talat i detta fall så allokerar algoritmen bara en variabel i som används i loop'en. Även om algoritmen allokerat några variabler till så beror mängden resurser inte på indatan/mängden data. Effektiviteten med avseende på resurser är alltså konstant!
För resurser presterar denna algoritm O(1). Vilket man hade betecknat alla algoritmer som är konstanta.
För att till fullo förklara Ordo så behöver vi komplettera med några räkneexempel. Säg att vi mätt och analyserat 3 algoritmer och formulerat ett uttryck för komplexiteten med avseende på indata/mängd data. Vi presenterar beräkningarna och komplexiteten uttryckt med Ordo:
| Uttryck | Ordo |
|---|---|
| 3n + 50 | O(n) |
| 2n2 + n + 10 | O(n2) |
| 0.5n3 | O(n3) |
Ordo "skalar" av t.ex. konstanter och sparar bara den term som "väger tyngst" i uttrycket. För jämförelser mellan två körningar av samma algoritm så är det endast Ordo som spelar roll.
Alltså om du optimerar en algoritm som är O(n) till att bli en faktor 2 snabbare så kommer fortfarande en körning med 3000 data att ta tre gånger så lång tid som en körning med 1000 data in din algoritm. I jämförelse så presterar din algoritm fortfarande O(n)!
Algoritmer som presterar olika, inte bara p.g.a. mängden data, utan beroende på vilken data som matas in i algoritmen blir lite svårare att analysera. Man brukar då undersöka tre fall:
- Bästa fallet. Då algoritmen blir klar snabbast.
- Sämsta fallet. Då algoritmen tar längst tid.
- Medelfallet. Statistikst hur algoritmen borde prestera överlag.
Det är inte alltid det finns ett bästa, sämsta eller medelfall för många algoritmer. Det kräver något mer komplexa algoritmer, t.ex. sorteringsalgoritmer för att kunna diskutera detta. Hur datan är organiserad, t.ex. i vilken ordning den kommer, måste påverka prestandan på algoritmen.
Sökalgoritmer
Som hörs på namnet så är detta algoritmer som söker upp något utifrån befintlig data eller samband. I skrivande stund finns det två artiklar som tar upp sökalgoritmer:
Den första artikeln är rekommenderad läsning för alla. Den andra, A*, är en väldigt speciell algoritm, rätt komplex, som används främst i spel.
Vi kan kika på en enkel sökalgoritm som letar efter största talet i en samling positiva heltal.
using System;
namespace Test
{
class Program
{
static void Main(string[] args)
{
int[] numbers = { 3, 6, 8, 2, 5, 1, 9 };
int max = 0;
for (int i = 0; i < numbers.Length; i++)
{
if(max < numbers[i])
max = numbers[i];
}
Console.WriteLine("Max var: " + max);
}
}
}
Övning 1
Kan du göra en komplexitetsanalys på algoritmen ovan (hitta max)? Analysera både snabbhet och resurser med avseende på mängden data som ska genomsökas.Sorteringsalgoritmer
Nu är vi inne på riktigt klassiskt område. Namnet avslöjar att det handlar om algoritmer som sorterar och skapar ordning i oreda. Det finns väldigt många varianter av sorteringsalgoritmer som sorterar främst tal. Vi har skrivit några artiklar redan:
Som exempel kan vi lyfta fram en variant av Bubble sort som hade mått bra av några optimeringar.
using System;
namespace Test
{
class Program
{
static void Main(string[] args)
{
int[] numbers = { 3, 6, 8, 2, 5, 1, 9 };
for (int j = 0; j < numbers.Length - 1; j++)
{
for (int i = 0; i < numbers.Length - 1; i++)
{
if(numbers[i] > numbers[i+1])
{
int tmp = numbers[i];
numbers[i] = numbers[i+1];
numbers[i+1] = tmp;
}
}
}
}
}
}
Övning 2
Kan du göra en komplexitetsanalys på algoritmen ovan (sortering)? Analysera både snabbhet och resurser med avseende på mängden data som ska genomsökas.Rekursiva algoritmer
Rekursiva algoritmer är algoritmer som är implementerade på ett visst vis. Det betyder att det finns både sök- och sorteringsalgoritmer som är rekursiva. Att en algoritm är rekursiv betyder att algoritmen "kallar på sig själv".
För att kalla, eller anropa, sig själv så måste algoritmen implementeras i en metod.
För att en rekursiv algoritm inte ska anropa sig själv i all evighet så krävs det också ett definierat basfall som talar om när algoritmen är klar.
Enligt Turing så klassificeras alla program som rekursiva och han gör istället en uppdelning i olika sorters rekursivitet. Vi definierar rekursiva program/algoritmer som sådana som "anropar sig själva" via metod och som har ett definierat basfall. Vi ska undersöka närmare vad Turing menade i en annan artikel.
Anledningen till att Turing kallar alla program för rekursiva är för att alla program kan skrivas om till att vara rekursiva. Omvänt kan man tyvärr inte alltid säga att alla rekursiva algoritmer kan skrivas om till att inte använda rekursivitet. Men faktum är att de flesta algoritmer som vanligtvis är rekursiva kan skrivas om utan rekursivitet.
Vi tar ett exempel där vi med en loop skriver ut talen 0 till 10.
using System;
namespace Test
{
class Program
{
static void Main(string[] args)
{
for (int i = 0; i <= 10; i++)
{
Console.WriteLine(i);
}
}
}
}
För att skriva om exemplet ovan till att använda rekursivitet så behöver vi införa en metod och ett basfall.
using System;
namespace Test
{
class Program
{
static void Main(string[] args)
{
SkrivUtTal(0);
}
static void SkrivUtTal(int i)
{
if (i > 10)
return;
Console.WriteLine(i);
SkrivUtTal(i + 1);
}
}
}
Detta kanske är det enklaste exemplet på en rekursiv algoritm. Vi måste anropa SkrivUtTal en första gång med det värde (0) som gäller första gången. Jämför detta med loop'en i första exemplet då vi deklarerar i=0.
Det algoritmen, metoden SkrivUtTal, gör är endast att skriva ut talet och sedan anropa sig själv med ett större värde. Detta hade kunnat upprepas i det oändliga om inte basfallet spärrar! Den spärr som tidigt avslutar (rad 14) algoritmen när talet blivit för stort (> 10) ser till att vi "nystar upp" alla anrop vi gjort och återvänder till programmet där vi för första gången anropade SkrivUtTal.
Rekursivitet är svårt att förstå fullt ut, speciellt om man inte vet hur en dator faktiskt fungerar. Varje gång en metod anropas så lagras den punkt (adress) i programmet där du befann dig på i ett speciellt minne som kallas stacken. Sedan när metoden är klar eller når en return så vet stacken vart i programmet vi skall återvända till. Skulle metoden i sig anropa en annan, eller samma, metod så skrivs det fler adresser till stacken. Totalt sett kommer exemplet ovan att skriva 12 adresser på stacken innan basfallet nås och anropen "nystas upp" genom att via stacken återvända 12 gånger för att till slut återvända till den plats i programmet som först anropade SkrivUtTal.
Varför 12 gånger? Jo 11 tal skrivs ut totalt (0 till 10) sedan anropas SkrivUtTal en extra gång och då når vi basfallet. Alltså totalt sett 12 anrop till SkrivUtTal.
Vi har bara kort nuddat vid begreppet rekursivitet i denna artikel. I en fördjupande artikel kommer vi att ta upp betydligt mer.
Senaste kommentarer