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(n2), O(n3) eller O(2n). – 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]
en enkel men ofta tidskrävande metod för att sortera. – Bubbelsortering kan användas för att sortera tal i nummerordning, ord i bokstavsordning eller för annan sortering i en fastställd ordning (linjär ordning). – Bubbelsortering går till så att ett program går igenom talen (eller bokstäverna) i den ordning de är givna, från början till slut, två intilliggande tal i taget. De två första talen jämförs, och om det andra talet är lägre än det första låter programmet dem byta plats. Sedan jämför programmet det andra talet med det tredje talet på samma sätt, och så vidare tills programmet kommer till slutet av talserien. Då börjar proceduren om från början. Detta upprepas till programmet kan gå igenom hela talserien utan att göra en enda omflyttning. Då är talen ordnade i storleksordning (eller orden i bokstavsordning) och programmet avslutas. Exempel:
41352 > 14352 > 13452 > 13425 > (ny genomgång:) 13425 > 13245 > 12345> (slutliga genomgången:) 12345.
– När man ska sortera stora mängder är bubbelsortering tidskrävande jämfört med andra metoder, och det används nästan aldrig i praktiken. En nackdel är att programmet inte vet när mängden är sorterad, utan upptäcker det först när det kan gå igenom hela mängden utan att ändra något. Även om programmet bara behöver göra en enda omflyttning måste det ändå gå igenom hela talserien två gånger. – Vad som ofta gör bubbelsortering ineffektivt är att höga tal snabbt rör sig bakåt (alltså till sin rätta plats) i mängden, medan låga tal rör sig långsamt framåt – ett steg per genomgång. Höga tal tidigt i den ursprungliga talserien kallas därför för kaniner, låga tal långt bak i serien kallas för sköldpaddor. Ett enda lågt tal långt bak i den ursprungliga talserien kan göra att programkörningen tar många gånger längre tid än vad den annars skulle göra. – På engelska: bubble sort. – Benämningen syftar på att låga tal ”bubblar” upp till sin rätta plats. – Läs mer i Wikipedia.
[data] [ändrad 2 april 2020]
(merge sort) – sortering av stora mängder data genom att man delar upp datamängden i delar som sorteras var för sig och sedan slås ihop. – Det kan till exempel gälla sortering i bokstavsordning eller i nummerordning. Programmet för klyvsortering delar upp datamängden i två delar, som sedan i sin tur kan delas upp i två delar och så vidare. Sedan sorterar programmet delarna var för sig. Detta går snabbare än att sortera hela mängden i ett svep. Förklaringen är att sortering går långsammare och långsammare ju mer data som ska sorteras. Men att passa ihop två mängder som redan är sorterade var för sig går snabbt. Nackdelen är att klyvsortering kräver mer minne än enkel sortering (heap sort).
[data] [ändrad 14 januari 2020]
- – sortering i bokstavsordning (eller annan standardordning);
- – ordnande av innehållet i en databas i en bestämd ordning; att kollatera (to collate);
- – på tryckerier: att se till att tryckarken kommer i rätt ordning (så att bokens sidor kommer i rätt följd).
–På engelska: collation.
[databaser] [språk] [tryckning] [ändrad 30 maj 2020]