PricingLoginStart free
DSA Interview Prep · Lektion

Analysera loopar och nästlade loopar

Beräkna tidskomplexiteten för enkla loopar, nästlade loopar och loopar med krympande intervall, till exempel binärsökning eller triangeliterationer.

Lektion 2 av 413 steg

Analysera loopar och nästlade loopar är en gratis lektion i DSA Interview Prep på CoddyKit. Detta är lektion 2 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för DSA Interview Prep, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.

En enkel loop: O(n)

Den enklaste loopen kör sin kropp n gånger och är därför O(n). Ett större steg ändrar antalet körningar, men inte klassen. Börja alltid med att räkna hur många gånger kroppen körs. 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ästlade loopar: O(n²) och mer

Två nästlade loopar som körs n gånger vardera ger n × n = O(n^2); tre ger O(n^3). Men om den inre loopen körs ett fast antal gånger förblir hela algoritmen linjä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)

Triangulär loop: O(n²/2) = O(n²)

När den inre loopen börjar vid i+1 bildar iterationerna en triangel: n(n-1)/2, vilket fortfarande är O(n^2) när faktorn en halv utelämnas. Problem med alla unika par ser ut så här.

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

Loop med krympande intervall: O(log n)

När loopvariabeln halveras i varje steg får du O(log n). Nyckelfrågan är: krymper intervallet 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ästlad loop med krympande inre loop: O(n log n)

En yttre loop som körs n gånger tillsammans med en inre loop på O(log n) ger O(n log n) — samma struktur som mergesortering. Att upptäcka ett inre steg på O(log n) är nyckeln till att analysera sorteringar.

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

Beroende inre loopar

När den inre loopens intervall beror på det yttre indexet ska du räkna totala iterationer, inte iterationer per steg. En inre loop som körs från 0 till i ger summan 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

Analysera bubblesortering steg för steg

Bubblesortering gör n(n-1)/2 jämförelser och har därför komplexiteten O(n^2). Även med tidigt avslut behöver en omvänt sorterad indata alla jämförelser. För långsam för stora indata.

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

Loopar över strängar och delsträngar

Var uppmärksam: Pythons slicing har komplexiteten O(k), det är inte kostnadsfritt, och strängkonkatenering med + i en loop har komplexiteten O(n^2) eftersom strängen kopieras varje gång. Använd ''.join(parts) i stället. 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'

Flera indataparametrar

Med två indata kan komplexiteten använda båda: O(m + n) för separat arbete och O(m × n) för nästlat arbete. Grafer anges ofta som O(V + E). Namnge varje variabel tydligt.

# 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

Nästling av loopar kontra sekventiella anrop

Ett funktionsanrop är inte kostnadsfritt — dess inre loop räknas också. Anropar du en hjälpfunktion på O(n) n gånger får du O(n^2). Titta alltid inuti svarta lådor när du analyserar.

# 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]

Praktik: identifiera komplexitet med en blick

Skapa en vana: räkna hur djupt looparna är nästlade, kontrollera om den inre loopen beror på den yttre och var uppmärksam på dolda kostnader i funktionsanrop och slicing. Koden är ett pussel att prova.

# 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)

Snabbtest

Snabbtest — se hur väl knepen för loopanalys fastnade. Lita på ditt resonemang här. 💪

Besvara frågan i den interaktiva lektionen

Lektionssammanfattning

Sammanfattning: nästlade loopar multipliceras och oberoende loopar adderas, en inre loop som halverar ger O(n log n), och dolda kostnader i anrop och slicing måste också räknas med.

Gratis att börja

Lär dig Python med en AI-lärare – gratis

Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.

Kurser
30
Lektioner
120
Börja lära dig gratisVisa hela kursen

Vanliga frågor

Är lektionen ”Analysera loopar och nästlade loopar” gratis?

Ja – du kan läsa vilka 3 lektioner som helst i lärvägen DSA Interview Prep, inklusive ”Analysera loopar och nästlade loopar”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.

Vad lär jag mig i ”Analysera loopar och nästlade loopar”?

Beräkna tidskomplexiteten för enkla loopar, nästlade loopar och loopar med krympande intervall, till exempel binärsökning eller triangeliterationer. Ni övar på DSA Interview Prep med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.

Behöver jag någon erfarenhet för att börja lära mig DSA Interview Prep?

Du behöver inga förkunskaper. Utbildningen i DSA Interview Prep på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 2 av 4.

Hur lång tid tar lektionen ”Analysera loopar och nästlade loopar”?

De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.

Kan jag skriva och köra kod i den här DSA Interview Prep-lektionen?

Ja. Varje DSA Interview Prep-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.

Alla lektioner i den här kursen

  1. Big-O-notation från grunden
  2. Analysera loopar och nästlade loopar
  3. Rekursion och metoden med rekursionsträd
  4. Rymdkomplexitet och avvägningar
← Tillbaka till DSA Interview Prep