Big-O-notation: tidskomplexitet

Optimera kod i Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Vad är tidskomplexitet?

Tidskomplexitet: mått på hur körtiden växer med indatans storlek
Hjälper till att besvara: "Vad händer när min data blir 10× större?"
Fokuserar inte på absolut tid

Big-O-notation

Matematisk notation för att beskriva värsta tänkbara scenario.

Några vanliga komplexitetsklasser:

O(1): Konstant tid – storleksoberoende

Förstå O(1)

Ett exempel på en O(1)-operation är ArrayLists get()

Intern (förenklad) implementation för en ArrayList som innehåller Strings:

public class ArrayList {}
    private String[] data; // Internal array
    private int size;

    // Get operation - direct array access
    public String get(int index) {
        return data[index]; // O(1)
    }
}

Big-O-notation

Matematisk notation för att beskriva värsta tänkbara scenario

Några vanliga komplexitetsklasser:

O(1): Konstant tid – storleksoberoende
O(n): Linjär tid – växer med indatans storlek

Förstå O(n)

Ett liknande exempel, men för ArrayLists contains()

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    // Linear search through array
    for (int i = 0; i < size; i++) {
        if (o.equals(elementData[i])) {
            return i;
        }
    }
    return -1; // Not found
}

Big-O-notation

Matematisk notation för att beskriva värsta tänkbara scenario

Några vanliga komplexitetsklasser:

O(1): Konstant tid – storleksoberoende
O(n): Linjär tid – växer med indatans storlek
O(n²): Kvadratisk tid – växer kvadratiskt med indatans storlek

Ett praktiskt exempel med kvadratisk komplexitet

// Finding a pair of numbers that sum to a target value
// Time complexity: O(n²)

public int[] findPairWithSum(ArrayList<Integer> numbers, int targetSum) {
    for (int i = 0; i < numbers.size(); i++) {
        for (int j = i + 1; j < numbers.size(); j++) {
            if (numbers.get(i) + numbers.get(j) == targetSum) {
                console.log("Found them!")
            }
        }
    }
}

Varför tidskomplexitet spelar roll

Effekt av indatans storlek:

O(1): 1 000 -> 1 000 000 element = Samma tid!
O(n): 1 000 -> 1 000 000 element = 1 000× långsammare
O(n²): 1 000 -> 1 000 000 element = 1 000 000× långsammare

Screenshot 2025-05-10 at 2.27.06 PM.png

Nu kör vi en övning!

Optimera kod i Java