Programmeringsmetodik: Vi lär oss det där med data: Grunderna om komplexitet

Tidskomplexitet handlar om hur lång tid det tar att köra ett program eller en algoritm. Men det handlar inte så mycket om ifall det tar 7 eller 8 sekunder, utan om hur tiden ändras när mängden data ändras. Om ett program ska sortera 1000 personer i skonummerordning, och det programmet tar 10 sekunder att köra, hur lång tid kommer det då att ta om vi i stället ska sortera 2000 personer? 10000? En miljon?

Exempel 1: Hus

För att illustrera tidskomplexitet ska vi börja med några exempel som inte handlar om programmering. Vi börjar med tre ganska kubformade hus:

En hundkoja En lagerlokal NASA:s Vehicle Assembly Building
Den här hundkojan är 1 meter hög, 1 meter bred och 1 meter djup. Den här lagerlokalen är (tänker vi oss) 10 meter x 10 meter x 10 meter. Vehicle Assembly Building, där NASA monterar ihop rymdraketer, är (tänker vi oss) 100 meter x 100 meter x 100 meter.

Alltså:

Hur lång tid tar det att att plantera blommor runt ytterväggen?

Låt oss säga att det tar 1 timme att plantera blommor runt ytterväggen på hundkojan. Då tar det förmodligen 10 timmar att plantera blommor runt lagerlokalen, och 100 timmar runt VAB.

Lagerlokalen är ju 10 gånger större än hundkojan, med ytterväggar som är 10 gånger längre, och då tar det, kan vi gissa, 10 gånger längre tid att plantera blommor. VAB är 100 gånger större än hundkojan, med ytterväggar som är 100 gånger längre, och då tar det, kan vi gissa, 100 gånger längre tid att plantera blommor.

Det här är vad vi kallar linjär tidskomplexitet, eller som man brukar skriva, O(n) (uttalas ordo-n):

(Man skiljer egentligen på olika sorters tidskomplexitet: maxtid, genomsnittstid och minsta tid. Men det struntar vi i här. Och så finns det rumskomplexitet. Det struntar vi också i.)

Hur lång tid tar det att att måla golvet?

Låt oss säga att det tar 1 timme att måla golvet i hundkojan. Då tar det förmodligen 100 timmar att måla golvet i lagerlokalen, och 10000 timmar i VAB.

Lagerlokalen är 10 gånger större än hundkojan, men ytan på golvet är 10*10 gånger större. Därför tar det, kan vi gissa, 10*10, dvs 100 gånger längre tid att måla golvet. VAB är 100 gånger större än hundkojan, med ett golv som har 100*100 gånger större yta, och då tar det, kan vi gissa, 100*100, dvs 10000 gånger längre tid att måla golvet.

Det här är vad vi kallar kvadratisk tidskomplexitet, eller som man brukar skriva, O(n2) (uttalas ordo-n-2):

Hur lång tid tar det att fylla huset med pingisbollar?

Låt oss säga att det tar 7 timmar att fylla hundkojan med pingisbollar. Då tar det förmodligen 7000 timmar att fylla lagerlokalen, och 7 miljoner timmar i VAB.

Lagerlokalen är 10 gånger större än hundkojan, men volymen inuti är 10*10*10 gånger större. Därför tar det, kan vi gissa, 1000 gånger längre tid att fylla upp den. VAB är 100 gånger större än hundkojan, med en innervolym som är 100*100*100 gånger större. Därför tar det, kan vi gissa, en miljon gånger längre tid att fylla upp den.

Det här är vad vi kan kalla kubisk tidskomplexitet, eller som man brukar skriva, O(n3) (uttalas ordo-n-3):

Hur lång tid tar det att att ta ett kort av huset?

Det spelar ingen roll hur stort huset är, utan det tar alltid lika lång tid att sikta med kameran och ta kortet. (Låt oss säga 3 sekunder.)

Det här är vad vi kallar konstant tid, eller som man brukar skriva, O(1) (uttalas ordo-1):

Skilj på tid och tidskomplexitet!

Tidskomplexitet är förstås relaterat till den tid det tar att utföra en uppgift, men det är inte riktigt samma sak. Tidskomplexitet handlar om hur tiderna förändras när mängden data som ska hanteras ändras, och inte om hur långa tiderna verkligen är.

Vi kan kalla den riktiga tiden (som man mäter med en klocka) för att utföra en uppgift för Tid(n). Till exempel kan Tid(n) för en viss uppgift vara 3n sekunder, så att med n=1 tar det 3 sekunder, med n=2 tar det 6 sekunder, med n=10 tar det 30 sekunder, och så vidare. Men tidskomplexiteten är fortfarande linjär, och skrivs O(n), inte O(3n).

Vi kommer att förklara mer längre ner om hur olika riktiga tider kan översättas till tidskomplexitet.

Exempel 2: Ballonger

En liten ballong En luftballong. Licens: Creative Commons Attribution-Share Alike 3.0 Unported
En liten ballong. En stor ballong.

En ballong med diametern 1 dm tar (tänker vi oss) 1 minut att blåsa upp, 1 minut att måla och 2 sekunder att titta på. Då kan vi räkna ut att:

Gör det någon skillnad egentligen?

Här har vi ritat upp ett diagram över hur lång tid tre olika program tar att köra. Vi ser att den blå kurvan, med kvadratisk tidskomplexitet, sticker iväg väldigt snabbt mot mycket långa tider, medan den röda kurvan, med linjär tidskomplexitet, ökar mycket långsammare:

O(1), O(n) och O(n2)

Sen visar vi samma bild igen, men med en annan skala på y-axeln. Notera hur både O(1) och O(n) knappt verkar stiga alls, jämfört med O(n2):

O(1), O(n) och O(n2)

Ett annat sätt att visa hur snabbt O(n2) ökar, jämfört med O(1) och O(n), är den här tabellen, som visar (avrundade) tider, om vi antar att formlerna anger sekunder körtid:

Antal indata O(1)-programmet O(n)-programmet O(n2)-programmet
1 17 sekunder 1 sekund 1 sekund
10 17 sekunder 10 sekunder 2 minuter
100 17 sekunder 2 minuter 3 timmar
1000 17 sekunder 17 minuter 12 dygn
1 miljon 17 sekunder 12 dygn 30000 år

Vi ser alltså att när mängden data växer, så kan skillnaderna i körtid bli stora mellan program med olika tidskomplexitet. En körning med en miljon indata tar alltså 12 dygn med det här O(n)-programmet, vilket man kanske kan stå ut med för en stor och viktig datakörning, till exempel en vetenskaplig simulering, men det är nog inte många som vill vänta i 30000 år på O(n2)-programmet.

Man struntar i konstanter

När problemet som vi ska lösa blir 100 gånger större, så är vi intresserade av hur mycket längre tid det tar. Tar det lika lång tid, 100 gånger längre tid, 10000 gånger längre tid, eller kanske en miljon gånger längre tid? Vi bryr oss inte så mycket om ifall det från början tog 3.7, 8.2 eller kanske 42 sekunder. Därför struntar vi i konstanter.

Vi kan ibland ange en formel för den riktiga tiden, i sekunder, för att lösa ett problem. Men denna riktiga tid är inte samma sak som tidskomplexiteten. Vi kan ta några exempel:

Riktig tid Tidskomplexitet Tidsökning om n blir 10 gånger större
Tid(n) = n O(n) 10 gånger
Tid(n) = 1.02 n O(n) 10 gånger
Tid(n) = 1000000 n O(n) 10 gånger
Tid(n) = 0.00037 n O(n) 10 gånger

Därmed inte sagt att konstanterna aldrig är viktiga. En faktor 100 i körtid mellan två algoritmer kan mycket väl vara skillnaden mellan ett bra och ett oanvändbart program. Men det har inte med tidskomplexitet att göra.

Man bryr sig bara om den "dominerande termen"

Den verkliga tiden för att köra en algoritm är ofta mer komplicerad än bara n2 och n3. Man kanske måste ha med flera termer, som i n3 + n2 + n. Men det gör inte så mycket, för när vi håller på med tidskomplexitet struntar vi i de "mindre" termerna (i det här fallet n2 och n) och bryr oss bara om den största (n3).

När problemen är "små", dvs n är litet, så spelar algoritmens tidskomplexitet oftast inte så stor roll. Det är först när problemen blir stora, dvs n är stort, som det blir viktigt. Till exempel kanske en sorteringsalgoritm med tidskomplexiteten O(n3) fungerar jättebra för upp till något hundratal element som man ska sortera, men den blir olidligt långsam med 1000 element, och den tar flera veckor att köra med 10000. Med en miljon element tar den tusentals år.

Därför koncentrerar man sig på stora n när man håller på med tidskomplexitet. Och då kommer termerna med högre exponent att dominera. Säg till exempel att den verkliga tiden, i sekunder, för en algoritm anges av formeln:

Tid(n) = n3 + n2 + n + 1

Med små n måste man räkna med alla fyra termerna (n3, n2, n och 1), men ju större n blir, desto mer dominerar n3. Redan vid n = 10 står n3 för 90 procent av resultatet:

n Tid(n) Bara termen n3
1 4 1 (25%)
2 15 8 (53%)
3 40 27 (68%)
4 85 64 (75%)
10 1111 1000 (90%)
100 1010101 1000000 (99%)
1000 1001001001 1000000000 (99.9%)

Därför struntar vi i alla termer utom den "dominerande", som (lite förenklat) är den med högst exponent. Exempel:

Riktig tid Tidskomplexitet Tidsökning om n ökar från 1 miljon till 10 miljoner
Tid(n) = n + 1 O(n) 9.99999 gånger
Tid(n) = 17n + 1 O(n) 9.999999 gånger
Tid(n) = 17n + 10000 O(n) 9.99471 gånger
Tid(n) = 0.01 n + 4711 O(n) 7.11 gånger
Tid(n) = n4 + 1000 n3 + 2000 n2 + 33 O(n4) 9991 gånger

Därmed inte sagt att de andra termerna aldrig är viktiga. En konstantterm på en vecka, som kan ses som att det tar en vecka att överhuvudtaget köra igång programmet innan det börjar räkna, gör nog väldigt ofta programmet oanvändbart.

Kuriosa: Den naiva algoritmen för matrismultiplikation, dvs den som man får om man tittar efter i sin mattebok hur matrismultiplikation går till och sen skriver en sån funktion, har tidskomplexiteten O(n3). Men det finns andra algoritmer som med hjälp av olika trick kan snabba upp matrismultiplikationen. Den algoritm som har bäst tidskomplexitet är Coppersmith-Winograds algoritm, med en tidskomplexitet på O(n2.376). Man skulle kunna tro att det betyder att den är snabbast. Tyvärr ingår det också en mycket stor konstantterm, som döljs av ordo-notationen, så Coppersmith-Winograds algoritm är tyvärr bara snabbast för matriser som är så stora att de inte kan hanteras med dagens datorer. (Källa: Engelska Wikipedias artiklar om matrismultiplikation och Coppersmith-Winograds algoritm.)

Några andra tidskomplexiteter

Jämförelser

Här har vi några olika kurvor, som visar hur tiden växer med storleken på indata för fem program som är O(1), O(log n), O(n), O(n log n) och O(n2).

O(1), O(log n), O(n), O(n log n) och O(n2)

Till exempel ser vi att O(log n) är en "bra" tidskomplexitet, för den växer mycket långsamt.

Här har vi dessutom lagt till O(n3) och O(n!):

O(1), O(log n), O(n), O(n log n), O(n2), O(n3) och O(n!)

(Vi har använt gamma-funktionen för att plotta x!. Skalan är också annorlunda, så att de nya kurvorna ska få plats.)

n3 växer så snabbt att nu ser n2 riktigt snäll ut. Och n! bara försvinner upp i skyn som en raket.

Några exempel med programkod

Summera talen i en array med längden n: O(n)
    int a[N];
    int summan = 0;
    for (int i = 0; i < N; ++i)
        summan += a[i];
Summera talen i en länkad lista med längden n: också O(n)
    struct link* this_link = first_link;
    int summan = 0;
    while (this_link != NULL) {
        summan += this_link->talet;
        this_link = this_link->next;
    }
Summera talen i en nxn-matris: O(n2)
    int m[N][N];
    int summan = 0;
    for (int x = 0; x < N; ++x)
        for (int y = 0; y < N; ++y)
            summan += m[x][y];
Summera en diagonal i samma nxn-matris: O(n)
    int m[N][N];
    int summan = 0;
    for (int x = 0; x < N; ++x)
        summan += m[x][x];
Summera båda diagonalerna i nxn-matrisen: O(n)
    int m[N][N];
    int summan = 0;
    for (int x = 0; x < N; ++x)
        summan += m[x][x];
    for (int x = 0; x < N; ++x)
        summan += m[x][N-x-1];
Summera talen i en tredimensionell nxnxn-matris: O(n3)
    int m[N][N][N];
    int summan = 0;
    for (int x = 0; x < N; ++x)
        for (int y = 0; y < N; ++y)
            for (int z = 0; z < N; ++z)
                summan += m[x][y][z];
Ofta kan man helt enkelt räkna antalet nästlade loopar. Men ibland kan man bli lurad. Anta till exempel att vi ska räkna antalet förekomster av bokstaven 'A' i en sträng med längden n.

Den här lösningen är O(n2), för funktionen strlen går igenom hela strängen och räknar antalet tecken, och det måste göras i loopvillkoret i varje varv i loopen, dvs vi går igenom hela strängen en gång för varje tecken i strängen:

    char* s = ......
    int antal = 0;
    for (int i = 0; i < strlen(s); ++i)
        if (s[i] == 'A')
            ++antal;
Den här lösningen däremot är O(n):
    char* s = ......
    int antal = 0;
    int n = strlen(s);
    for (int i = 0; i < n; ++i)
        if (s[i] == 'A')
            ++antal;

Läs mer


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 23 augusti 2012