|
|
|
|
| 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å:
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):
| Det här är egentligen en förenkling som man brukar göra. Stora O som vi använt ska egentligen vara Θ, den grekiska bokstaven theta eller thäta (på engelska theta), och det finns också Ω (omega), och θ (lilla theta) och ω (lilla omega). Dessutom skiljer man på maxtid, minsta tid och genomsnittstid. Men det struntar vi i här. Och så finns det rumskomplexitet, inte bara tidskomplexitet. Det struntar vi också i. |
(De grekiska bokstäverna i rutan ovan kanske inte syns i alla webbläsare, så den finns också som en bild: grekiska-bokstaver.png.)
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):
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):
Det här är vad vi kallar konstant tid, eller som man brukar skriva, O(1) (uttalas ordo-1).
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.
|
|
| En liten ballong. | En stor ballong. |
Sen visar vi samma bild igen, men med ett längre intervall av x-axeln en annan skala på y-axeln. Nu syns det tydligare hur både O(1) och O(n) knappt verkar stiga alls, jämfört med 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.
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.
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. I oktober 2022 var den bästa kända komplexiteten för en matrismultiplikationsalgoritm O(n2.37188). 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å den algoritmen är bara snabbast för matriser som är så stora att de inte kan hanteras med dagens datorer. Den kan kallas en "galaktisk algoritm". En galaktisk algoritm är en som överträffar alla andra algoritmer för problem som är tillräckligt stora, men där "tillräckligt stor" är så stort att algoritmen aldrig används i praktiken. Galaktiska algoritmer kallas så för att de aldrig kommer att användas på några datamängder på jorden. (Källa: Engelska Wikipedias artikel om Computational complexity of matrix multiplication) |
Till exempel ser vi att O(log n) är en "bra" tidskomplexitet, för den växer mycket långsamt.
Här nedan har vi dessutom lagt till O(n3) och O(n!). Skalan är annorlunda, så de nya kurvorna ska få plats.
(Vi har använt gamma-funktionen för att plotta n!.)
n3 växer så snabbt att nu ser n2 riktigt snäll ut. Och n! bara försvinner upp i skyn som en raket.
En exponentiell funktion är av typen f(x) = ax. I bilden här nedan visar vi som förut Tid(n) = n2, Tid(n) = n3 och Tid(n) = n!. Dessutom har vi lagt till Tid(n) = 2n, som är en exponentiell funktion, och alltså växer exponentiellt.
Vi ser att Tid(n) = 2n växer snabbare än Tid(n) = n3, och när n blir stort växer den snabbare än alla polynom, dvs snabbare än Tid(n) = na för alla a. Däremot växer Tid(n) = n! fortfarande allra snabbast.
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;