8 svar
80 visningar
mattenerd är nöjd med hjälpen!
mattenerd 6
Postad: 11 okt 2018 Redigerad: 11 okt 2018

Tidskomplexitet - träd

Hej! 

Jag har skrivit en algoritm som givet en array a, returnerar en ny array indices där varje element i a är utbytt mot det index som tillhör det minsta större elementet till höger om elementet och som sedan printar varje element i den nya arrayen. Så för till exempel a = [4,5,8,1,9], så kommer indices = [1,2,4,4,-1]. Om det inte finns något sådant större element så skrivs -1 dit istället. Den fungerar som den ska, men jag är lite osäker på vad tidskomplexiteten är och hur man går tillväga för att reda på den? För att således kunna se hur effektiv min lösning är. 

Laguna 749
Postad: 11 okt 2018 Redigerad: 11 okt 2018

Vad har TreeMap-metoderna för komplexitet? 

IGIL 65
Postad: 11 okt 2018 Redigerad: 11 okt 2018

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). 


Laguna 749
Postad: 11 okt 2018 Redigerad: 11 okt 2018

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. 

mattenerd 6
Postad: 11 okt 2018

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

mattenerd 6
Postad: 11 okt 2018

 @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). 

Laguna 749
Postad: 12 okt 2018

Då blir det O(nlogn).

Laguna 749
Postad: 12 okt 2018

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).

mattenerd 6
Postad: 12 okt 2018

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

Svara Avbryt
Close