Jag förstår att det inte är helt lätt att förstå utan att detta är något som kräver att man tänker några gånger. Ett sätt som fungerade bra för mig att lära mig O-notation är att analysera sorteringsalgoritmer.
För att ta ett enkelt exempel, säg att du har en lista med 4 element: [8, 2, 5, 4] som du vill sortera. Det finns en enkel algoritm som heter Bubble Sort. Den går igenom hela listan och jämför två element i taget som är jämte varandra. Är det vänstra elementet större än det högra så byter vi plats på dom. När vi når slutet på listan börjar vi om så vida vi inte har bytt plats på något element, har vi inte det är vi klara.
Algoritmen fungerar då så här:
Iteration 1:
=> [8, 2, 5, 4]
Kontrollera element på plats 0 och 1 i listan, d.v.s. jämför 8 och 2. Vi ser att 8 > 2, därför byter vi plats på dom.
=> [2, 8, 5, 4]
Kontrollera element på plats 1 och 2 i listan, d.v.s. 8 > 5. Byt plats.
=> [2, 5, 8, 4]
Kontrollera element på plats 2 och 3 i listan. 8 > 4. Byt plats.
=> [2, 5, 4, 8]
Iteration 1 klar. Bytte vi plats på något under iteration, ja flera gånger. Kör en iteration till:
Iteration 2:
[2, 5, 4, 8] => kolla 2 > 5. Byt inte plats.
[2, 5, 4, 8] => kollar 5 > 4. Byt plats!
[2, 4, 5, 8] => kolla 5 > 8. Byt inte plats.
Iteration 2 klar. Bytte vi plats på något. Ja - en iteration till.
Iteration 3:
[2, 4, 5, 8] => 2 > 4? Byt inte plats.
[2, 4, 5, 8] => 4 > 5? Byt inte plats.
[2, 4, 5, 8] => 5 > 8? Byt inte plats.
Iteration 3 klar. Bytte vi plats på något? Nej. Klar!
Så, vad säger oss nu detta? För att kunna prata om algoritmens effektivitet måste vi analysera hur den beter sig i generella fall. Vi kan göra detta på flera sätt genom att t.ex. betrakta hur algoritmen beter sig för olika input. Är listan nästan sorterad behöver vi bara ett litet antal iterationer. I andra fall behöver vi dock många fler.
Låt oss nu anta att vi har en lista med n element som är så dåligt sorterad den kan vara, d.v.s. alla element ligger på ett sådant sätt att just vår Bubble Sort-algoritm kommer flytta runt alla element ett maximalt antal gånger. Vi har byggt ett vorst case scenario helt enkelt.
Vi kan då härleda (går inte in på det här för att fatta mig kort) att vi måste köra maximalt n stycken iterationer - och vi vet ju att i varje iteration går vi igenom hela listan en gång och den innehåller n st element. Alltså kräver vår algoritm att vi går igenom vår lista med n st element, n st gånger => n*n = n^2.
Vi kan då säga att vår Bubble Sort sorterar vår lista inom O(n^2), där n syftar på antalet element i vår lista. I olika algoritmer kan n syfta på olika saker men ofta handlar det om inputens storlek.
När man pratar om big-O eller ordo förenklar vi ofta. Säg att vi gör ett extra steg som resulterar i att vi istället får ett uttryck O(2*n^2) så är vi inte intresserade av konstanten framför för i det stora hela är 2*n^2 ungefär n^2, speciellt när n är stort, därför slänger vi ofta bort alla konstanter inom O-uttrycket. Det är dock enormt stor skillnad på n^2 och n^3, speciellt när vår input n är stor. På så sätt blir vi jätteglada om vi kan lösa ett problem inom O(n^2) istället för O(n^3) men det spelar mindre roll om vi löser det inom O(100*n^2) eller O(n^2) - tänk själv skillnaden om n är en miljard.
I ditt exempel säger vi att din algoritm är linjär, d.v.s. O(50) = O(2 * 25) = O(25) = O(n). Ändrar vi storleken på n (t.ex. dubblar n i detta fallet) ökar tiden för vår algoritm linjärt, medan om vi skulle ha O(n^2) skulle tiden öka kvadratiskt (d.v.s. mycket mer!).
Nu har jag bara skrapat på ytan och försökt förklara enkelt men detta ämnet är otroligt intressant men ofta överväldigande att börja med.
Utöver O (Big-O eller Ordo) kan vi även mäta tidskomplexiteten på "tightare" sätt, vi kan också vilja ta hänsyn till annat än inputens storlek - kanske kräver vår algoritm väldigt mycket minne, men jag tror jag nöjer mig här så jag inte bara skriver en wall of text som förvirrar mer än den hjälper.
En bra bok för den intresserade är Introduction to Algorithms: http://en.wikipedia.org/wiki/Introduction_to_Algorithms
Tror även den finns som online-kurs någonstans. Det är dock som sagt ett tungt ämne som är svårt att greppa utan handledning.
Fråga gärna om du vill veta mer!
