Una funzione ricorsiva può essere…
diretta o indiretta
Una soluzione è ricorsiva se può essere espressa come…
S(D) = f(S(D’))
S(D_0) = S_0
In S(D) = f(S(D’)), S(D_0) = S_0 cosa indica l’ultima condizione?
Indica che ogni algoritmo deve terminare e che la ritorsione ha un numero di passi finito
In che modo la dimensione n dei dati si può ridurre in una chiamata ricorsiva?
Si può ridurre di un valore costante (decrease) o di un fattore costante (divide)
Da cosa è data la complessità nel tempo?
T(n) = D(n) + T(n’) + C(n)
Qual è la forma generale della complessità nel tempo di una ricorsione divide and conquer e di una decrease and conquer?
- divide: T(n) = D(n) + aT(n/b) + C(n)
- decrease: T(n) = D(n) + sum_{i = 0} ^ {a-1} (n - k_i) + C(n)
Definizione di Stack
ADT che supporta operazioni di push e pop, tipo LIFO
Definizione e caratteristiche di stack frame
Struttura dati che contiene parametri formali, viabili locali, indirizzi di ritorno della funzione, puntatore al codice della funzione. Viene creato e distrutto a ogni chiamata e se ce ne sono troppi può esserci stack overflow. Gli stack frame vengono memorizzati nello stack di sistema
cosa contiene lo SP
indirizzo del primo SF disponibile
come crescono gli indirizzi dello stack?
da maggiori a minori
definizione e caratteristiche di funzione tail-recursive
funzione in cui la chiamata ricorsiva è l’ultima operazione
- solo discesa -> più efficiente
- la chiamata successiva sostituisce la precedente
- no stack overflow
- no stack -> trasformabile direttamente in iterativa
Caratteristiche del merge sort (no complessità)
- il vettore viene diviso ogni volta al centro
- chiamata ricorsiva nel vettore sx e dx
- terminazione: quando il vettore ha un solo elemento -> ordinato
- fusione dei due sottovettori (lì avviene il vero e proprio ordinamento)
- stabile, non in loco
Complessità del merge sort
libro, comunque NlogN
caratteristiche del quicksort (no complessità)
- divisione non per forza al centro
- partizione con pivot
- in loco, non stabile
- terminazione: sottovettore di un elemento
complessità del quick sort e della partiton
- partition: theta(n)
- quick, caso peggiore: un sottovettore di n-1 elementi e l’altro di un solo elemento, il pivot è il min o il max -> O(n^2)
- quick, caso medio e migliore: sottovettori di n/2 -> O(nlogn)
codice della void MergeSort(Item *A, int N) e quindi delle void MergeSortR(Item *A, Item *B, int l, int r) e void Merge(Item *A, Item *B, int l, int q, int r)
appunti
codice della void QuickSort(Item *A, int N) e quindi delle void QuickSortR(Item *A, int l, int r) e int partition(Item *A, int l, int r)
appunit
