DSA Interview Prep · leksjon

Analyse av løkker og nøstede løkker

Beregn tidskompleksiteten for enkeltløkker, nøstede løkker og løkker med krympende intervaller, som binærsøk eller trekantiterasjoner.

Leksjon 2 av 413 trinn

Analyse av løkker og nøstede løkker er en gratis leksjon i DSA Interview Prep på CoddyKit. Dette er leksjon 2 av 4. Du kan lese valgfritt 3 leksjoner fra denne læringsstien gratis i sin helhet – deretter låser CoddyKit PRO opp alle leksjoner, samt praktisk øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i DSA Interview Prep, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.

Enkel løkke: O(n)

Den enkleste løkken kjører kroppen sin n ganger, så den er O(n). Et større steg endrer antallet, men ikke klassen. Begynn alltid med å telle hvor ofte kroppen kjører. Se koden.

# O(n): body runs n times
def count_ops_linear(n):
    ops = 0
    for i in range(n):
        ops += 1     # constant work
    return ops

print(count_ops_linear(100))  # 100

# Still O(n): step=2 halves count but same class
def count_ops_half(n):
    ops = 0
    for i in range(0, n, 2):
        ops += 1
    return ops

print(count_ops_half(100))    # 50  => O(n)

Nøstede løkker: O(n²) og mer

To løkker som er nøstet og hver kjører n ganger, gir n x n = O(n^2); tre gir O(n^3). Men hvis den indre løkken kjører et fast antall ganger, forblir helheten lineær.

def count_pairs(n):
    ops = 0
    for i in range(n):          # n iterations
        for j in range(n):      # n iterations each
            ops += 1
    return ops

print(count_pairs(10))   # 100 = 10^2
print(count_pairs(100))  # 10000 = 100^2
# Doubling n quadruples ops: classic O(n^2)

Trekantløkke: O(n²/2) = O(n²)

Når den indre løkken starter på i+1, danner iterasjonene en trekant: n(n-1)/2, som fortsatt er O(n^2) etter at halvdelen er utelatt. Problemer med alle unike par ser slik ut.

def count_unique_pairs(n):
    ops = 0
    for i in range(n):          # n iterations
        for j in range(i+1, n): # n-1, n-2, ..., 0
            ops += 1
    return ops

print(count_unique_pairs(10))  # 45 = 10*9/2
print(count_unique_pairs(100)) # 4950
# Still O(n^2) -- constant factor 1/2 dropped

Løkke med krympende område: O(log n)

Når løkkevariabelen halveres i hvert steg, får De O(log n). Det avgjørende spørsmålet er: krymper området multiplikativt (log n) eller additivt (n)? Se koden.

def count_log_ops(n):
    ops = 0
    i = n
    while i >= 1:
        ops += 1
        i //= 2   # halve each iteration
    return ops

import math
for n in [8, 16, 64, 1024]:
    ops = count_log_ops(n)
    print(f'n={n}, ops={ops}, log2={int(math.log2(n))}')
# ops tracks log2(n) closely

Nøstet løkke med krympende indre løkke: O(n log n)

En ytre løkke som kjører n ganger, med en indre løkke på O(log n), gir O(n log n) – det samme mønsteret som i flettesortering. Å oppdage et indre steg på O(log n) er nøkkelen til å analysere sorteringsalgoritmer.

import math

def count_n_log_n(n):
    ops = 0
    for i in range(n):    # n iterations
        j = n
        while j >= 1:     # log n iterations
            ops += 1
            j //= 2
    return ops

for n in [8, 32, 128]:
    ops = count_n_log_n(n)
    predicted = int(n * math.log2(n))
    print(f'n={n}: actual={ops}, n*log2(n)~={predicted}')

Avhengige indre løkker

Når området til den indre løkken avhenger av den ytre indeksen, skal De telle totalt antall iterasjoner, ikke antallet per steg. En indre løkke som går fra 0 til i, summeres til n(n-1)/2 = O(n^2). Se koden.

# Inner loop runs i times: total = 0+1+2+...+(n-1) = n(n-1)/2 => O(n^2)
def sum_inner_i(n):
    ops = 0
    for i in range(n):
        for j in range(i):   # runs 0,1,2,...,n-1 times
            ops += 1
    return ops

print(sum_inner_i(10))  # 45 = 10*9/2  => O(n^2)

# Inner loop runs n/i times (i doubles): sum ≈ n*log n => O(n log n)
def sum_inner_n_over_i(n):
    ops = 0
    i = 1
    while i <= n:
        for j in range(n // i):
            ops += 1
        i *= 2
    return ops
print(sum_inner_n_over_i(64))  # ~ 64*6 = 384

Analyse av boblesortering trinn for trinn

Boblesortering sammenligner n(n-1)/2 ganger, så den er O(n^2). Selv med tidlig avslutning trenger omvendt sorterte inndata fortsatt alle sammenligningene. For tregt for store inndata.

def bubble_sort(arr):
    n = len(arr)
    comparisons = 0
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            comparisons += 1
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:  # early exit if sorted
            break
    return comparisons

arr = list(range(10, 0, -1))  # worst case: reversed
ops = bubble_sort(arr)
print(f'Sorted: {arr}')
print(f'Comparisons: {ops}')  # 45 = 10*9/2

Løkker over strenger og delstrenger

Vær oppmerksom: Python-slicing er O(k), ikke gratis, og strengsammenslåing med + i en løkke er O(n^2) fordi det kopieres hver gang. Bruk ''.join(parts) i stedet. Se koden.

# O(n^2): string concat in loop
def build_bad(n):
    s = ''
    for i in range(n):
        s += str(i)  # copies s each time!
    return s

# O(n): join is a single pass
def build_good(n):
    parts = []
    for i in range(n):
        parts.append(str(i))
    return ''.join(parts)

print(build_good(10))  # '0123456789'

Flere inndataparametere

Med to inndata kan kompleksiteten bruke begge: O(m + n) for separat arbeid, O(m x n) for nøstet arbeid. Grafer uttrykkes ofte som O(V + E). Gi hver variabel et tydelig navn.

# O(m + n): two independent loops
def independent(m, n):
    a = sum(range(m))  # O(m)
    b = sum(range(n))  # O(n)
    return a + b       # total O(m + n)

# O(m * n): nested
def nested(m, n):
    count = 0
    for i in range(m):     # O(m)
        for j in range(n): # O(n) each
            count += 1
    return count  # O(m * n)

print(independent(5, 10))  # 10 + 45 = 55
print(nested(5, 10))       # 50

Løkke-i-løkke kontra sekvensielle kall

Et funksjonskall er ikke gratis – den indre løkken teller også. Kaller De en hjelper på O(n) n ganger, får De O(n^2). Se alltid inne i kall som fungerer som svarte bokser når De analyserer.

# Naive string matching: O(n*m)
def naive_search(text, pattern):
    n, m = len(text), len(pattern)
    matches = []
    for i in range(n - m + 1):  # O(n)
        if text[i:i+m] == pattern:  # O(m) comparison + O(m) slice
            matches.append(i)
    return matches
# Total: O(n*m)

print(naive_search('abcabcabc', 'abc'))  # [0, 3, 6]

Praktisk: identifiser kompleksitet på et øyeblikk

Opparbeid en vane: tell hvor dypt løkkene er nøstet, sjekk om den indre løkken avhenger av den ytre, og se etter skjulte kostnader i funksjonskall og slicing. Koden er en oppgave De kan prøve.

# What is the complexity of this function?
def mystery(nums):
    result = []
    for i in range(len(nums)):          # O(n)
        for j in range(i, len(nums)):   # O(n) worst
            if sum(nums[i:j+1]) == 0:   # O(n) slice + sum!
                result.append((i, j))
    return result
# Answer: O(n^3)  -- three nested n-proportional ops
# Outer O(n) x inner O(n) x sum/slice O(n) = O(n^3)

Hurtigsjekk

Hurtigsjekk – se hvor godt triksene for løkkeanalyse har festet seg. Stol på egen resonnering her. 💪

Besvar den i den interaktive leksjonen

Oppsummering av leksjonen

Oppsummering: nøstede løkker multipliseres og uavhengige løkker adderes, en indre løkke som halverer gir O(n log n), og skjulte kostnader i kall og slicing må også telles med.

Gratis å komme i gang

Lær deg Python med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 30
Leksjoner: 120

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Analyse av løkker og nøstede løkker» gratis?

Ja – du kan lese valgfritt 3 av leksjonene i læringsstien DSA Interview Prep, inkludert «Analyse av løkker og nøstede løkker», gratis i sin helhet her på nettet. Deretter låser CoddyKit PRO opp alle leksjoner, samt interaktiv øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.

Hva lærer jeg i «Analyse av løkker og nøstede løkker»?

Beregn tidskompleksiteten for enkeltløkker, nøstede løkker og løkker med krympende intervaller, som binærsøk eller trekantiterasjoner. Du øver på DSA Interview Prep med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med DSA Interview Prep?

Ingen tidligere erfaring er nødvendig. DSA Interview Prep på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 2 av 4.

Hvor lang tid tar leksjonen «Analyse av løkker og nøstede løkker»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne DSA Interview Prep-leksjonen?

Ja. Alle DSA Interview Prep-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

← Tilbake til DSA Interview Prep