Forberedelse til kodeinterviews · Lektion

Analyse af løkker og indlejrede løkker

Beregn tidskompleksiteten for enkeltstående løkker, indlejrede løkker og løkker med krympende områder som binær søgning eller trekantsiterationer.

Lektion 2 af 413 trin

Analyse af løkker og indlejrede løkker er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 2 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.

Enkelt løkke: O(n)

Den enkleste løkke kører sin løkkekrop n gange, så den er O(n). Et større spring ændrer antallet, men ikke klassen. Begynd altid med at tælle, hvor ofte løkkekroppen kø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)

Indlejrede løkker: O(n²) og videre

To løkker, der er indlejret i hinanden og hver kører n gange, giver n × n = O(n^2); tre giver O(n^3). Men hvis den indre løkke kører et fast antal gange, forbliver det hele lineært.

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)

Trekantet løkke: O(n²/2) = O(n²)

Når den indre løkke begynder ved i+1, danner gentagelserne en trekant: n(n-1)/2, hvilket stadig er O(n^2), når den halve faktor fjernes. Problemer med alle unikke par ser sådan ud.

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økkevariablen halveres for hvert trin, får du O(log n). Det afgørende spørgsmål 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

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

En ydre løkke, der kører n gange, sammen med en indre løkke på O(log n) giver O(n log n) — det er formen på mergesort. At genkende et indre trin på O(log n) er nøglen til at analysere sorteringer.

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}')

Afhængige indre løkker

Når den indre løkkes område afhænger af det ydre indeks, skal du tælle det samlede antal gentagelser, ikke antallet pr. trin. En indre løkke fra 0..i giver summen 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 af boblesortering trin for trin

Boblesortering sammenligner n(n-1)/2 gange, så den er O(n^2). Selv med tidlig afslutning kræver sorteret inddata i omvendt rækkefølge stadig alle sammenligninger. For langsomt til store inddata.

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 strenge og delstrenge

Pas på: Pythons udsnit har kompleksiteten O(k), det er ikke gratis, og sammenkædning af strenge med + i en løkke er O(n^2), fordi der kopieres hver gang. Brug ''.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 inddata-parametre

Med to inddata kan kompleksiteten bruge begge: O(m + n) ved separat arbejde og O(m × n) ved indlejret arbejde. Grafer udtrykkes ofte som O(V + E). Navngiv hver variabel tydeligt.

# 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

Indlejrede løkker kontra sekventielle kald

Et funktionskald er ikke gratis — dets indre løkke tæller også. Kald en hjælpefunktion med O(n) n gange, så får du O(n^2). Se altid ind i funktioner, du ellers behandler som sorte bokse, når du 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: Identificer kompleksitet med et blik

Opbyg en vane: Tæl indlejringen af løkker, undersøg om den indre løkke afhænger af den ydre, og vær opmærksom på skjulte omkostninger i funktionskald og udsnit. Koden er en opgave, du 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)

Hurtigt tjek

Hurtigt tjek — se, hvor godt tricksene til løkkeanalyse sidder fast. Stol på din argumentation her. 💪

Besvar den i den interaktive lektion

Opsamling af lektionen

Opsamling: indlejrede løkker ganges, og uafhængige løkker lægges sammen. En indre løkke, der halverer, giver O(n log n), og skjulte omkostninger i kald og udsnit skal også tælles med.

Gratis at komme i gang

Lær Forberedelse til kodeinterviews med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser: 90
Lektioner: 360

Start gratis Se hele kurset

Ofte stillede spørgsmål

Er lektionen “Analyse af løkker og indlejrede løkker” gratis?

Ja — hele teksten til “Analyse af løkker og indlejrede løkker” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.

Hvad lærer jeg i “Analyse af løkker og indlejrede løkker”?

Beregn tidskompleksiteten for enkeltstående løkker, indlejrede løkker og løkker med krympende områder som binær søgning eller trekantsiterationer. Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.

Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?

Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 2 af 4.

Hvor lang tid tager lektionen “Analyse af løkker og indlejrede løkker”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?

Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Alle lektioner i dette kursus

← Tilbage til Forberedelse til kodeinterviews