Analizzare cicli e cicli annidati
Calcoli la complessità temporale di cicli singoli, cicli annidati e cicli con intervalli che si riducono, come nella ricerca binaria o nelle iterazioni triangolari
Analizzare cicli e cicli annidati è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Un singolo ciclo: O(n)
Il ciclo più semplice esegue il proprio corpo n volte, quindi è O(n). Un passo più grande cambia il numero di esecuzioni, ma non la classe. Inizi sempre contando quante volte viene eseguito il corpo. Veda il codice.
# 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)Cicli annidati: O(n²) e oltre
Due cicli annidati, ciascuno eseguito n volte, producono n x n = O(n^2); tre producono O(n^3). Se però il ciclo interno viene eseguito un numero fisso di volte, la complessità complessiva resta lineare.
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)Ciclo triangolare: O(n²/2) = O(n²)
Quando il ciclo interno inizia da i+1, le iterazioni formano un triangolo: n(n-1)/2, che resta comunque O(n^2) dopo aver eliminato la metà. I problemi che richiedono tutte le coppie distinte hanno questa struttura.
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 droppedCiclo su un intervallo decrescente: O(log n)
Quando la variabile del ciclo viene dimezzata a ogni passaggio, si ottiene O(log n). La domanda chiave è: l'intervallo si riduce moltiplicativamente (log n) o additivamente (n)? Veda il codice.
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) closelyCiclo annidato con interno decrescente: O(n log n)
Un ciclo esterno eseguito n volte con un ciclo interno O(log n) produce O(n log n), la struttura tipica del merge sort. Riconoscere un passaggio interno O(log n) è fondamentale per analizzare gli algoritmi di ordinamento.
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}')Cicli interni dipendenti
Quando l'intervallo del ciclo interno dipende dall'indice esterno, conti le iterazioni totali, non quelle di ogni singolo passaggio. Un ciclo interno da 0 a i produce la somma n(n-1)/2 = O(n^2). Veda il codice.
# 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 = 384Analisi del bubble sort passo dopo passo
Il bubble sort esegue n(n-1)/2 confronti, quindi è O(n^2). Anche con un'uscita anticipata, un input ordinato al contrario richiede comunque ogni confronto. È troppo lento per input di grandi dimensioni.
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/2Cicli su stringhe e sottostringhe
Attenzione: lo slicing in Python è O(k), non è gratuito, e la concatenazione di stringhe con + all'interno di un ciclo è O(n^2), perché ogni volta viene effettuata una copia. Usi invece ''.join(parts). Veda il codice.
# 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'Più parametri di input
Con due input, la complessità può usare entrambi: O(m + n) per operazioni separate, O(m x n) per operazioni annidate. I grafi spesso si esprimono come O(V + E). Assegni un nome chiaro a ogni variabile.
# 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)) # 50Cicli annidati e chiamate sequenziali
Una chiamata di funzione non è gratuita: conta anche il suo ciclo interno. Chiamando n volte una funzione di supporto O(n), si ottiene O(n^2). Durante l'analisi, esamini sempre l'interno delle chiamate apparentemente opache.
# 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]Pratica: identificare la complessità a colpo d'occhio
Coltivi questa abitudine: conti il livello di annidamento dei cicli, verifichi se il ciclo interno dipende da quello esterno e cerchi i costi nascosti nelle chiamate di funzione e nello slicing. Il codice è un enigma da provare a risolvere.
# 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)Verifica rapida
Verifica rapida: vediamo quanto sono rimasti impressi i trucchi per analizzare i cicli. Si fidi del suo ragionamento. 💪
Riepilogo della lezione
Riepilogo: i cicli annidati si moltiplicano e quelli indipendenti si sommano; un ciclo interno che dimezza l'intervallo produce O(n log n), e bisogna contare anche i costi nascosti nelle chiamate e nello slicing.
Domande Frequenti
La lezione «Analizzare cicli e cicli annidati» è gratuita?
Sì — il testo completo di «Analizzare cicli e cicli annidati» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Analizzare cicli e cicli annidati»?
Calcoli la complessità temporale di cicli singoli, cicli annidati e cicli con intervalli che si riducono, come nella ricerca binaria o nelle iterazioni triangolari Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Analizzare cicli e cicli annidati»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- La notazione Big-O dalle basi
- Analizzare cicli e cicli annidati
- Ricorsione e metodo dell'albero ricorsivo
- Complessità spaziale e compromessi