The Big O
Vi läser för tillfället en kurs i datastrukturer och algoritmer där vi gått igenom notationen för O(n), annars kallat för The Big O.
Har inte riktigt förstått genom föreläsningar och anteckningar exakt hur man beräknar detta. Till exempel så har vi fått en fråga där vi ska anta hur lång tid en algoritm av komplexiteten O(n^2) tar.
Det vi fått som information är att O(n^2) algoritmen tar 20 sekunder att köra för storleken n = 1 000 000.
Då ska vi kunna anta hur lång tid det skulle ta för algoritmen om vi sätter n = 2 000 000 istället.
Av min research online så har jag förstått de som att om man dubblar n för en algoritm av komplexitet O(n^2) så ska de ta ungefär 4 ggr så lång tid för algoritmen att köra.
Har jag förstått det helt fel då?
Det är rätt. Ordo beskriver algoritmens effektivitet, hur många deloperationer den använder.
O(n) är linjär, dubblas n så fördubblas arbetet/tiden.
O(n^2) är kvadratisk, dubblas n så ökar arbetet/tiden med kvadraten dvs 4. (2n)^2/(n^2)=4.
Exempel: Bubbelsortering.
O(n*logn) ligger däremellan och är vanligt för sorteringsalgoritmer.
Exempel: Quick sort (även om den har fall då den urartar till O(n^2)).
Eller merge sort, som är att föredra. Den har O(n*logn) också.
