Tidskomplexitet - träd

Vad har TreeMap-metoderna för komplexitet? 

Vad är tidskomplexitet?

Tidskomplexitet är ett datavetenskapligt uttryck som handlar om hur lång tid det tar för en algoritm att köra, beroende på hur mycket data som vi ger den (input). 

Hur skrivs tidskomplexitet?

När man skriver tidskomplexiteten för en algoritm brukar man använda sig av skrivsättet Ordo (BigOh). Skrivsättet går ut på att definiera hur lång tid det går att köra en algoritm med t.ex n antal data/input. Vanliga skriv sättet är O(), O står för Ordo (BigOh).

Exempel på tidskomplexitet:

Vi börjar med en algoritm som bara skriver ut texten "IGIL".

Kod:

public static void skrivUt(String[] lista) {
    System.out.println( "IGIL" );
}

Oavsett hur stor lista vi skickar med (input), kommer antalet instruktioner vara lika många. Vi anger tidskomplexiteten som O(1).

Graf:

(Y-axel = antal instruktioner/snabbhet ; X-axel = antal element i listan (input) ; Siffergradering är inte aktuell)

Som vi ser i grafen kommer antalet instruktioner alltid vara 1 oavsett antalet element i listan.

Låt oss kolla på hur det ser ut ifall vi skriver ut alla namn i en lista.

Kod:

public static void skrivUt(String[] lista) {
    for (int i = 0; i < lista.length; i++) {
        System.out.println( lista[i] );
    }
}

I denna metod har vi en for-loop. Om vi skickar in en lista med 100 namn kommer for-loopen köras 100 gånger. Om vi istället skickar med en lista med 1000 namn kommer for-loopen köras 1000 gånger. Hur lång tid det tar för algoritmen att köras beror på listan (input). Det kan skrivas som O(n).

Graf:

(Y-axel = antal instruktioner/snabbhet ; X-axel = antal element i listan (input) ; Siffergradering är inte aktuell)

Som grafen visar kommer det ta längre tid ju större våran lista är. Den växer linjärt.

Ett annat bra exempel är en sorterings algoritm, så som bubbelsortering.

Kod: 

public static void skrivUt(String[] lista) {
    for (int i = lista.length; i >= 0; i--) {
        for (int k = 0; k < i; k++) {
            //KOD HÄR
        }
    }
}

I denna metod har vi en for-loop i en annan for-loop. Detta kommer göra att den för varje värden den jobbar med i listan, måste gå igenom alla andra värden. Istället för att bara gå igenom listan en gång. Måste den gå igenom listan n * n gånger. Vilket då kan skrivas som O(n^2).

Graf: 

(Y-axel = antal instruktioner/snabbhet ; X-axel = antal element i listan (input) ; Siffergradering är inte aktuell)

Tiden kommer att öka exponentiellt, vilket inte är bra. 

Ett sista exempel. Vi har två for-loop:ar som är efter varandra och gör något.

Kod:

public static void skrivUt(String[] lista) {
    for (int i = lista.length; i >= 0; i--) {
        //NÅGOT
    }
    for (int i = 0; i < 0; i++) {
        //NÅGOT
    }
}

Denna gång kommer vi att köra igenom listan en gång, och sedan köra igenom listan igen. For-looparna är inte i varandra. Här så kommer första for-loopen köra igenom alla element n i listan, och sedan kör den andra for-loopen igenom alla element n i listan. Tiden kan skrivas O(2n)

Graf:

(Y-axel = antal instruktioner/snabbhet ; X-axel = antal element i listan (input) ; Siffergradering är inte aktuell)

Hur lång tid tar min algoritm?

Det finns inte så vitt jag vet, ett sätt att direkt räkna ut sin tidskomplexitet. Det handlar om att uppskatta. I mina exempel så ser vi att det går att koppla tiden till en graf. Detta är viktigt att tänka på eftersom det är just det man gör. Skapar en funktion som beskriver tiden beroende på input. Ett bra sätt är att kolla på olika algoritmer och se vilken tidkomplexitet de har. En annan viktigt del är just att kolla på vilka loopar som finns i algoritmen. For-loop blir lätta eftersom man kan oftast koppla dem till O(n), medans andra loopar som while kan göra så det mer komplext, så som O(log(n)), beroende på vad som finns i while loopen.

https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it

Länken kan vara till hjälp med att lära dig uppskatta tidskomplexiteten!

Din algoritms tidskomplexitet:

I din algoritm finns det en for-loop. Du går igenom hela listan med tal mer eller mindre rakt av. Tiden som det kommer ta att köra algoritmen ökar linjärt med antalet tal i din lista. Därför uppskattar jag att den får en tidskomplexitet på O(n). 

Man kan ju alltid prova empiriskt: generera slumpmässiga arrayer och ta reda på hur lång tid det tar, automatiskt. Jag blir förvånad om det är linjärt, men man behöver kanske stora arrayer för att se det. 

@Laguna Tree-map metoderna har tidskomplexitet log(n). 

 @IGIL Tack för ett så långt och tydligt svar! Det blev mycket klarare för mig nu. Jag är dock lite osäker på om det är tidskomplexitet O(n) eftersom Tree-map metoderna, higherKey() och get() också har tidskomplexitet som är O(log n). 

Då blir det O(nlogn).

Det är viktigt att veta inte bara komplexiteten i medeltal utan den värsta det kan bli ("worst case"). Jag gissar att det värsta fallet för trädmetoderna fortfarande är O(logn), men det är inte alltid så. Om träden kan bli obalanserade kan de vara O(n).

@Laguna Tack så jättemycket! TreeMap i Java är ett själv-balanserat träd så det borde vara okej.