Rilasciato · in miglioramento
Algorithm
Divide et impera scompone un problema in sottoproblemi più piccoli, li risolve ricorsivamente e ne combina i risultati, come nel merge sort.
Divide et impera è una tecnica di progettazione degli algoritmi: si scompone un problema in istanze più piccole dello stesso problema (dividere), le si risolve ricorsivamente (conquistare) e dai loro risultati si costruisce la risposta finale (combinare). Merge sort, ricerca binaria, esponenziazione rapida, quickselect, moltiplicazione di Karatsuba e la ricerca della coppia di punti più vicina seguono tutti questo schema.
È importante perché spesso trasforma una soluzione a forza bruta O(n^2) in O(n log n) o persino O(log n). L'idea chiave di calcolare nel passo di combinazione le informazioni che attraversano la divisione, come nel conteggio delle inversioni, ricorre spesso nei colloqui tecnici, e le stesse idee sono alla base delle librerie di ordinamento, della moltiplicazione di grandi numeri, della FFT e dell'esponenziazione modulare in crittografia.
Inizia tracciando a mano il merge sort per assimilare dividere, conquistare e combinare, poi esercitati a impostare ricorrenze come T(n) = aT(n/b) + f(n) e a risolverle con il teorema dell'esperto (master theorem). Quindi implementa da solo il conteggio delle inversioni, l'esponenziazione rapida e quickselect, e impara a riconoscere quando sottoproblemi sovrapposti richiedono invece la programmazione dinamica.
Dividere l'input, risolvere le parti ricorsivamente e combinare le risposte. Un caso base ferma la ricorsione e il costo della combinazione di solito determina il tempo di esecuzione.
Il tempo si scrive come T(n) = aT(n/b) + f(n); confrontando f(n) con n^(log_b a) si ottengono risultati come O(n log n) per il merge sort.
Gestire in tempo lineare i casi che toccano entrambe le metà, come nel conteggio delle inversioni o nel sottoarray massimo, è l'idea centrale.
Se resta un solo sottoproblema, come nella ricerca binaria, nell'esponenziazione rapida e in quickselect, si ottengono algoritmi O(log n) o O(n) atteso.
sort_count ordina la lista con il merge sort e, ogni volta che un elemento della metà destra viene preso per primo, aggiunge il numero di elementi ancora in attesa a sinistra: così conta le inversioni in O(n log n). power è l'esponenziazione rapida: dimezza l'esponente ed eleva al quadrato, quindi bastano O(log e) moltiplicazioni. Eseguendo python divide_and_conquer.py si stampano la lista ordinata con le sue 14 inversioni e 3^200 modulo 1.000.000.007.
divide_and_conquer.py
def sort_count(a):
"""Return (sorted list, number of inversions) using merge sort."""
if len(a) <= 1:
return list(a), 0
mid = len(a) // 2
left, x = sort_count(a[:mid])
right, y = sort_count(a[mid:])
merged, i, j, cross = [], 0, 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
cross += len(left) - i # right[j] is smaller than every left[i:]
merged += left[i:] + right[j:]
return merged, x + y + cross
def power(base, exp, mod):
"""base ** exp % mod with O(log exp) multiplications."""
if exp == 0:
return 1 % mod
half = power(base, exp // 2, mod)
result = half * half % mod
return result * base % mod if exp % 2 else result
if __name__ == "__main__":
print(sort_count([5, 2, 4, 7, 1, 3, 2, 6])) # ([1, 2, 2, 3, 4, 5, 6, 7], 14)
print(power(3, 200, 1_000_000_007)) # 136318165
python divide_and_conquer.pySei capitoli che ti accompagnano dall'installazione ai concetti chiave di Divide et impera.
Fai domande, condividi la tua esperienza e scambia opinioni su Divide et impera.
Ancora nessuna discussione. Avvia la prima.
0 commenti
Accedi · Accedi per lasciare un commento.
Scrivi tu il primo commento.