Algoritmer og problemløsning

Big OCopy Anchor Link

Big O beskriver, hvordan arbejdet vokser med inputtet:

• O(1): dictionary-opslag.
• O(log n): binary search i sorterede data.
• O(n): én gennemgang af en list.
• O(n log n): effektiv sortering.
• O(n²): to indlejrede gennemgange.

Binary searchCopy Anchor Link

def binary_search(values: list[int], target: int) -> int | None:
    low, high = 0, len(values) - 1

    while low <= high:
        middle = (low + high) // 2
        if values[middle] == target:
            return middle
        if values[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return None

Binary search kræver sorterede værdier. Uden den forudsætning er resultatet forkert.

RecursionCopy Anchor Link

En rekursiv funktion skal have et base case og nærme sig det ved hvert kald. Til meget dybe problemer er en eksplicit stack ofte bedre i Python.

Dynamic programmingCopy Anchor Link

Gem resultater af overlappende delproblemer med caching eller byg løsningen nedefra i en tabel. Det kan ændre en eksponentiel løsning til en lineær.

GraferCopy Anchor Link

Brug BFS til korteste vej i en uvægtet graf og DFS til gennemløb, komponenter og cycle detection. En adjacency list er normalt en dictionary med sets eller lists.

ProblemløsningsmetodeCopy Anchor Link

1. Skriv input, output og edge cases.
2. Lav først en korrekt, simpel løsning.
3. Mål dens kompleksitet.
4. Vælg en datastruktur, der fjerner flaskehalsen.
5. Test tomt input, dubletter og grænseværdier.

ØvelseCopy Anchor Link

Find den korteste vej mellem to brugere i et socialt netværk. Implementér BFS, returnér selve ruten, og håndtér ukendte og afkoblede brugere.