Schema divide et impera
Ricavi da merge sort lo schema in tre passaggi (dividere, conquistare, combinare) e lo applichi sistematicamente a nuove tipologie di problemi.
Schema divide et impera è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 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.
Che cos'è il Divide et impera
Divide et impera (D&C) risolve un problema suddividendolo in sottoproblemi indipendenti dello stesso tipo, risolvendo ciascuno ricorsivamente e combinandone le soluzioni. La parola chiave è indipendenti: i sottoproblemi non condividono lo stato, a differenza della programmazione dinamica, in cui si sovrappongono. Esempi classici: merge sort, ricerca binaria, quick sort, coppia di punti più vicini e moltiplicazione veloce di matrici. D&C raggiunge in genere un tempo O(n log n) attraverso il modello in tre passaggi.
# Divide and Conquer vs DP:
# D&C: sub-problems are INDEPENDENT (no overlap)
# DP: sub-problems OVERLAP (same sub-problem solved multiple times)
# D&C examples:
# Merge sort: split array in half, sort each, merge
# Binary search: check midpoint, recurse on one half
# Max subarray (D&C): find max in left half, right half, crossing
# Recurrence pattern:
# T(n) = 2T(n/2) + O(n) → O(n log n) [merge sort]
# T(n) = T(n/2) + O(1) → O(log n) [binary search]
# T(n) = T(n/k) + O(n) → O(n log_k n) [k-way split]Il modello in tre passaggi
Ogni algoritmo D&C segue tre passaggi: (1) Divide — suddividere il problema in due o più sottoproblemi più piccoli, in genere nel punto medio. (2) Conquer — risolvere ricorsivamente ciascun sottoproblema. Definire un caso base per terminare la ricorsione, di solito n ≤ 1. (3) Combine — unire o combinare le soluzioni dei sottoproblemi nella soluzione complessiva. La creatività risiede interamente nel passaggio Combine; Divide consiste in genere semplicemente nel dividere il problema nel punto medio.
def divide_and_conquer(arr, lo, hi):
# BASE CASE: trivial sub-problem
if lo >= hi:
return base_case_result(arr, lo, hi)
# DIVIDE: split at midpoint
mid = (lo + hi) // 2
# CONQUER: solve sub-problems recursively
left_result = divide_and_conquer(arr, lo, mid)
right_result = divide_and_conquer(arr, mid + 1, hi)
# COMBINE: merge results
return combine(left_result, right_result, arr, lo, mid, hi)
def base_case_result(arr, lo, hi): return arr[lo]
def combine(l, r, arr, lo, mid, hi): return max(l, r)Merge sort come esempio canonico
Merge sort illustra perfettamente D&C: Divide l'array nel punto medio. Conquer ordinando ricorsivamente ciascuna metà. Combine unendo le due metà ordinate in O(n). È nella fase di merge che viene svolto tutto il lavoro. Ricorrenza: T(n) = 2T(n/2) + O(n). Per il caso 2 del Master Theorem: T(n) = O(n log n). Questa è la ricorrenza D&C più importante da memorizzare.
def merge_sort(arr):
# BASE CASE
if len(arr) <= 1:
return arr
# DIVIDE
mid = len(arr) // 2
# CONQUER
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# COMBINE
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
return result + left[i:] + right[j:]
print(merge_sort([5, 3, 8, 1, 9, 2])) # [1,2,3,5,8,9]Riferimento rapido al Master Theorem
Il Master Theorem risolve ricorrenze della forma T(n) = aT(n/b) + f(n): Caso 1: f(n) = O(n^(log_b(a) - ε)) → T(n) = O(n^log_b(a)). Caso 2: f(n) = O(n^log_b(a)) → T(n) = O(n^log_b(a) × log n). Caso 3: f(n) = Ω(n^(log_b(a) + ε)) → T(n) = O(f(n)). Merge sort: a=2, b=2, f(n)=O(n), n^log_2(2)=n → Caso 2 → O(n log n).
# Master Theorem quick examples:
# T(n) = 2T(n/2) + O(n) → a=2,b=2,f=n,n^log2(2)=n → Case2 → O(n log n)
# T(n) = 2T(n/2) + O(1) → a=2,b=2,f=1,n^1=n >> 1 → Case1 → O(n)
# T(n) = 2T(n/2) + O(n^2) → a=2,b=2,f=n^2,n^1 << n^2 → Case3 → O(n^2)
# T(n) = T(n/2) + O(1) → a=1,b=2,f=1,n^log2(1)=1=f → Case2 → O(log n)
# T(n) = T(n/3)+T(2n/3)+O(n) → Master doesn't apply directly → O(n log n) by recursion tree
recurrences = [
('Merge sort: 2T(n/2)+n', 'O(n log n)'),
('Binary search: T(n/2)+1', 'O(log n)'),
('Naive matrix mult: 8T(n/2)+n^2', 'O(n^3)'),
('Strassen: 7T(n/2)+n^2', 'O(n^2.81)'),
]
for r, sol in recurrences: print(r, '->', sol)Maximum Subarray: approccio D&C
L'approccio D&C a Maximum Subarray: la risposta si trova interamente nella metà sinistra, interamente nella metà destra oppure attraversa il punto medio. Nel caso in cui attraversi il punto medio, si procede verso sinistra a partire da mid e verso destra a partire da mid+1, calcolando la somma massima in ciascuna direzione, per poi combinare i risultati. Questo approccio D&C O(n log n) è più lento dell'approccio O(n) di Kadane, ma illustra perfettamente il modello ed è una domanda comune nei colloqui su D&C.
def max_subarray_dc(nums, lo=None, hi=None):
if lo is None: lo, hi = 0, len(nums) - 1
if lo == hi: return nums[lo]
mid = (lo + hi) // 2
# Conquer
left_max = max_subarray_dc(nums, lo, mid)
right_max = max_subarray_dc(nums, mid + 1, hi)
# Cross-midpoint sum
left_sum = curr = 0
for i in range(mid, lo - 1, -1):
curr += nums[i]
left_sum = max(left_sum, curr)
right_sum = curr = 0
for i in range(mid + 1, hi + 1):
curr += nums[i]
right_sum = max(right_sum, curr)
cross_max = left_sum + right_sum
return max(left_max, right_max, cross_max)
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_dc(nums)) # 6Funzione di potenza: esponenziazione rapida
Fast Power (LeetCode 50): calcolare x^n in O(log n) usando D&C. Se n è pari: x^n = (x^(n/2))^2. Se n è dispari: x^n = x × x^(n-1). Gestire n negativo con x^(-n) = 1/x^n. Ogni chiamata ricorsiva dimezza n, quindi la profondità è O(log n). Questo è un esempio chiaro in cui il passaggio Combine consiste semplicemente in una moltiplicazione: banale, ma efficace.
def my_pow(x, n):
if n < 0:
return 1 / my_pow(x, -n)
# BASE CASE
if n == 0: return 1
# DIVIDE and CONQUER
half = my_pow(x, n // 2)
if n % 2 == 0:
return half * half # even: x^n = (x^(n/2))^2
else:
return x * half * half # odd: x^n = x * (x^(n/2))^2
print(my_pow(2, 10)) # 1024
print(my_pow(2, -2)) # 0.25
print(my_pow(3, 5)) # 243
print(my_pow(0, 0)) # 1Sorted Array to BST
Convert Sorted Array to BST (LeetCode 108) usa D&C: si sceglie il punto medio come radice, garantendo così l'equilibrio dell'altezza, quindi si costruiscono ricorsivamente il sottoalbero sinistro a partire dalla metà sinistra e il sottoalbero destro a partire dalla metà destra. Si ottiene così un BST bilanciato in altezza con altezza minima O(log n). La struttura D&C ricalca la ricerca binaria: a ogni livello della ricorsione, il punto medio diventa la radice dell'intervallo corrente.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def sorted_array_to_bst(nums):
def helper(lo, hi):
if lo > hi: return None
mid = (lo + hi) // 2
node = TreeNode(nums[mid]) # DIVIDE at midpoint
node.left = helper(lo, mid - 1) # CONQUER left
node.right = helper(mid + 1, hi) # CONQUER right
# COMBINE: already done by assignment
return node
return helper(0, len(nums) - 1)
def inorder(node):
if not node: return []
return inorder(node.left) + [node.val] + inorder(node.right)
root = sorted_array_to_bst([-10, -3, 0, 5, 9])
print(inorder(root)) # [-10,-3,0,5,9] (sorted, proving BST property)Quando D&C non è la scelta migliore
D&C comporta un sovraccarico: profondità dello stack delle chiamate di funzione, slicing degli array (se non si usano gli indici) e fase di combinazione. È ottimale quando la fase di combinazione ha costo O(n) o inferiore. Quando i sottoproblemi si sovrappongono, D&C ricalcola le soluzioni inutilmente: è necessaria la programmazione dinamica. Quando la fase di combinazione domina, ad esempio con costo O(n²), D&C non migliora gli approcci ingenui. È importante sapere cosa scegliere: D&C per sottoproblemi indipendenti, DP per sottoproblemi sovrapposti.
# When D&C hurts:
# Fibonacci with pure D&C (no memo): T(n) = T(n-1) + T(n-2) → O(2^n)
# Sub-problems OVERLAP → use DP or memoisation instead
def fib_dc(n):
if n <= 1: return n
return fib_dc(n-1) + fib_dc(n-2) # O(2^n)!
def fib_dp(n):
a, b = 0, 1
for _ in range(n): a, b = b, a+b
return a # O(n)
print(fib_dp(30)) # fast
# fib_dc(40) would take seconds — do not run large values!D&C per la ricerca binaria in una matrice ordinata
La ricerca in una matrice 2D (LeetCode 240) in cui ogni riga e ogni colonna è ordinata può essere risolta con D&C: si parte dall'angolo in alto a destra. Se il valore corrente è > target, ci si sposta a sinistra ed si elimina la colonna. Se il valore corrente è < target, ci si sposta in basso e si elimina la riga. Se è uguale, l'elemento è stato trovato. Questo algoritmo O(m+n) non è tecnicamente un D&C ricorsivo, ma condivide l'idea chiave: eliminare metà dello spazio di ricerca a ogni passaggio.
def search_matrix(matrix, target):
if not matrix: return False
m, n = len(matrix), len(matrix[0])
row, col = 0, n - 1 # start top-right
while row < m and col >= 0:
val = matrix[row][col]
if val == target:
return True
elif val > target:
col -= 1 # eliminate this column
else:
row += 1 # eliminate this row
return False
matrix = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
print(search_matrix(matrix, 5)) # True
print(search_matrix(matrix, 20)) # FalseAnalisi dell'albero della ricorsione
Per le ricorrenze D&C che non rientrano nel Master Theorem, si utilizza il metodo dell'albero della ricorsione. Si disegna ogni livello delle chiamate ricorsive e si somma il lavoro svolto a ciascun livello. Merge sort: al livello k ci sono 2^k sottoproblemi di dimensione n/2^k. Lavoro per livello = 2^k × O(n/2^k) = O(n). Il numero totale di livelli = log n. Lavoro totale = O(n log n). Questo metodo visivo funziona per qualsiasi ricorrenza e aiuta a capire perché D&C raggiunge in genere O(n log n).
# Merge sort recursion tree analysis:
# Level 0: 1 problem of size n → O(n) work
# Level 1: 2 problems of size n/2 → 2*O(n/2) = O(n) work
# Level 2: 4 problems of size n/4 → 4*O(n/4) = O(n) work
# ...
# Level log(n): n problems of size 1 → n*O(1) = O(n) work
# Total levels = log(n)+1
# Total work = O(n) * O(log n) = O(n log n)
import math
n = 64
levels = int(math.log2(n)) + 1
print(f'n={n}: {levels} levels, {n}*{levels} = {n*levels} work units')
print(f'O(n log n) = O({n} * {int(math.log2(n))}) = O({n*int(math.log2(n))})')Come presentare D&C in un colloquio
Quando presenta una soluzione D&C in un colloquio: (1) esponga esplicitamente i tre passaggi: 'dividerò il problema nel punto medio, risolverò ricorsivamente ciascuna metà, quindi combinerò i risultati con un merge'. (2) Identifichi chiaramente il caso base. (3) Derivi la ricorrenza: T(n) = 2T(n/2) + O(n). (4) Applichi il Master Theorem o l'albero della ricorsione per ricavare O(n log n). (5) Indichi quando D&C è migliore o peggiore delle alternative (DP per i sottoproblemi sovrapposti, l'algoritmo di Kadane per il massimo sottarray).
# D&C interview template to memorize:
def dc_template(problem, lo, hi):
# 1. BASE CASE (state it first)
if lo == hi: return solve_base(problem, lo)
# 2. DIVIDE
mid = (lo + hi) // 2
# 3. CONQUER
left = dc_template(problem, lo, mid)
right = dc_template(problem, mid + 1, hi)
# 4. COMBINE (this is where the algorithm-specific logic goes)
return combine_results(left, right, problem, lo, mid, hi)
def solve_base(p, i): return p[i]
def combine_results(l, r, p, lo, mid, hi): return max(l, r)
print('D&C template: base-divide-conquer-combine')
print('Complexity usually: T(n)=2T(n/2)+O(n) → O(n log n)')Verifica rapida
Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: Divide et impera segue il modello: caso base → divisione nel punto medio → soluzione ricorsiva → combinazione, T(n) = 2T(n/2) + O(n) dà O(n log n) secondo il Caso 2 del Master Theorem e D&C è ottimale per i sottoproblemi indipendenti, mentre la programmazione dinamica è necessaria quando i sottoproblemi si sovrappongono. Nella prossima lezione applicheremo D&C per contare le inversioni in un array usando una versione modificata di merge sort.
Domande Frequenti
La lezione «Schema divide et impera» è gratuita?
Sì — il testo completo di «Schema divide et impera» è 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 «Schema divide et impera»?
Ricavi da merge sort lo schema in tre passaggi (dividere, conquistare, combinare) e lo applichi sistematicamente a nuove tipologie di problemi. 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 1 di 4.
Quanto tempo richiede la lezione «Schema divide et impera»?
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
- Schema divide et impera
- Conteggio delle inversioni con merge sort modificato
- Elemento maggioritario: voto di Boyer-Moore
- Mediana di due array ordinati