Tidskomplexitet och ordo-notation

Ordo (stora O) beskriver hur körtiden växer när indata växer — inte hur många sekunder något tar på just din dator.

Ordo	Namn	1 000 element	1 000 000 element
O(1)	konstant	1	1
O(log n)	logaritmisk	10	20
O(n)	linjär	1 000	1 000 000
O(n log n)	linjärlogaritmisk	10 000	20 000 000
O(n²)	kvadratisk	1 000 000	10¹² (för långsamt)

Konstanter och mindre termer stryks: 3n + 50 är O(n), n² + 1000n är O(n²).

def har_dubbletter_naivt(lista):     # O(n²) — två nästlade loopar
    for i in range(len(lista)):
        for j in range(i + 1, len(lista)):
            if lista[i] == lista[j]:
                return True
    return False

def har_dubbletter_snabbt(lista):    # O(n) — mängden kollar på konstant tid
    sedda = set()
    for x in lista:
        if x in sedda:
            return True
        sedda.add(x)
    return False

Med 10 000 element: den första gör ~50 miljoner jämförelser, den andra 10 000. På en miljon element är den första helt omöjlig medan den andra tar bråkdelar av en sekund.

Räkneregeln: en loop över n är O(n). En loop inuti en loop är O(n²). Halvering per steg är O(log n). Att sortera är O(n log n).

I AI: attention är O(T²) i sekvenslängden — det är därför långa kontexter är dyra, och därför man forskar på alternativ.