Arkiv: Ord

beteckning på ett sätt att uppskatta komplexiteten i typer av beräkningar. Noteras med bokstaven O och används för jämförelser av algoritmers effektivitet. – Antalet element i beräkningen, till exempel antalet ord som ska sorteras i bokstavsordning, ställs mot antalet steg i beräkningen. Då menar man inte antalet steg i ett specifikt fall, utan generellt för en typ av beräkning. Om det till exempel gäller att hitta ett ord i en lista som innehåller n ord är ordo O(n). Det vill säga att antalet steg i sökningen är proportionellt mot antalet ord i listan (n). Sedan kan det ju vara så att ordet man söker efter står först i listan, och då går sökningen fort, eller att ordet står sist i listan, och då tar sökningen lång tid. Det påverkar inte värdet på ordo. Det viktiga är att man aldrig behöver gå igenom listan mer än en gång för att hitta det sökta ordet. Ordo anger det största möjliga antalet steg i beräkningen (värsta fallet). – Andra beräkningar, till exempel att sortera tal i storleksordning eller ord i bokstavsordning, kräver att mängden tal respektive ord gås igenom flera gånger (om mängden inte redan står i rätt ordning). Då får man värden på ordo som O(n²), O(n³) eller O(2ⁿ). – När man beräknar ordo brukar man bortse från konstanter, och om beräkningen innehåller höga potenser kan man också bortse från lägre potenser. Att beräkna ordo är en överslagsberäkning, inte en exakt beräkning. – Man skiljer mellan stora O och lilla o: stora O anger det högsta möjliga värdet för antalet moment i en beräkning av viss typ, medan lilla o anger ett övre värde som inte kan uppnås, men nästan (ett asymptotiskt värde). – Det finns också omega (Ω), som anger det lägsta möjliga värdet, samt theta (θ) som säger att antalet moment i beräkningen är exakt proportionellt med funktionen av n.

[matematik] [programmering] [22 december 2020]