05: Relazioni di Ricorrenza

Una relazione di ricorrenza descrive il numero di operazioni eseguite da un algoritmo ricorsivo in funzione della dimensione dell'input. È utile per analizzare la complessità di algoritmi ricorsivi.

In una relazione di ricorrenza a partizione costante, ogni chiamata ricorsiva riduce la dimensione dell'input di una quantità costante. Ad esempio, calcolare il fattoriale di un numero, dove ad ogni chiamata ricorsiva si riduce l'input di 1.

In una relazione di ricorrenza a partizione bilanciata, ogni chiamata ricorsiva riduce la dimensione dell'input di un fattore costante. Ad esempio, l'algoritmo di merge-sort, dove ad ogni chiamata ricorsiva si divide l'input a metà.

Il metodo iterativo risolve una relazione di ricorrenza espandendo ricorsivamente la formula fino a ottenere un'espressione che non contiene più chiamate ricorsive. In questo modo, il numero di operazioni può essere calcolato in modo diretto.

Merge-sort è un algoritmo di ordinamento che divide l'input in due metà, ordina le due metà ricorsivamente, e poi le unisce in una singola sequenza ordinata.

Quick-sort è un algoritmo di ordinamento che sceglie un elemento pivot, partiziona l'input in base al pivot, ordina ricorsivamente le due sottosequenze e poi le unisce.

La procedura Partition è utilizzata per posizionare il "perno" al suo posto corretto nel vettore. Gli elementi minori del perno vengono spostati a sinistra e quelli maggiori a destra del perno. Il risultato è un vettore suddiviso in due sotto-vettori.

Il numero di operazioni eseguite dalla procedura Partition è proporzionale alla dimensione del sottovettore che deve riorganizzare. La complessità è indicata da TP(n) = an, dove n è la dimensione del sottovettore e a è una costante.

Nel caso peggiore, il "perno" scelto è sempre l'elemento minimo o massimo del sottovettore. In tal caso, una sola chiamata ricorsiva viene eseguita per ogni livello della ripartizione. Questo porta ad una maggiore complessità, con la relazione di ricorrenza T(n) = T(n-1) + an + b, dove a e b sono costanti.

L'algoritmo Quick-Sort può essere utilizzato per ordinare qualsiasi tipo di dati, come numeri, stringhe o oggetti. La sua efficienza dipende dalla scelta dei pivot e dall'implementazione della procedura Partition.

Un metodo per risolvere le relazioni di ricorrenza che consiste nell'espandere la relazione ricorsivamente fino a raggiungere un caso base.

Il caso base è il punto di arresto per la ricorsione. È il punto in cui la funzione non si chiama più ricorsivamente.

L'ordine di una relazione di ricorrenza è il numero di termini precedenti usati per calcolare il termine corrente.

La notazione asintotica che indica un limite superiore per la funzione. Una funzione f(n) è O(g(n)) se esiste una costante c e un valore n0 tale che f(n) ≤ c*g(n) per tutti gli n ≥ n0.

Il tempo richiesto per il caso peggiore dell'algoritmo QuickSort.

Un algoritmo di ordinamento che confronta e scambia elementi adiacenti fino a quando l'array non è ordinato.

Un algoritmo di ricerca binaria ricorsivo che trova la posizione di un elemento in un array ordinato.

Il caso peggiore per la ricerca binaria ricorsiva si verifica quando l'elemento cercato non è presente nell'array.

La complessità temporale del caso peggiore della ricerca binaria ricorsiva è logaritmica rispetto alla dimensione dell'array.

Dividere un array in due metà bilanciate.

Ordinare le due metà dell'array utilizzando ricorsivamente il merge sort.

Unire le due metà ordinate in un unico array ordinato.

Il merge sort è un algoritmo di ordinamento efficiente con una complessità temporale logaritmica.

La complessità di Merge-Sort è descritta da una relazione di ricorrenza che rappresenta il tempo necessario per ordinare un array di dimensione n. La relazione è composta da due casi: quando l'array ha un solo elemento (n=1), il tempo necessario è costante (a). Altrimenti, l'array viene diviso in due sottoarray di dimensioni n/2 e il tempo richiesto è la somma del tempo necessario per ordinare i due sottoarray (2T(n/2)), più il tempo necessario per combinare i due sottoarray ordinati (bn + c). La relazione di ricorrenza è quindi T(n) = a se n=1, altrimenti T(n) = 2T(n/2) + bn + c.

Il metodo dell'iterazione consiste nell'espandere la relazione di ricorrenza scrivendola ripetutamente per un numero di iterazioni fino a raggiungere un caso base. Questo metodo permette di esprimere la complessità temporale di Merge-Sort in funzione di n, la dimensione dell'array.

Dopo k ≤ log2 n iterazioni, il termine dominante e quindi la complessità temporale di Merge-Sort è T(n) = Θ(n log n). Questo risultato indica che Merge-Sort ha una complessità temporale logaritmica rispetto alla dimensione dell'array.

Il caso migliore di Quick-Sort si verifica quando il partizionamento divide il vettore in due parti uguali. In questo caso, la complessità temporale di Quick-Sort è uguale a quella di Merge-Sort, ovvero Θ(n log n).

Il tempo necessario per ordinare un array è proporzionale alla dimensione dell'array moltiplicato per il logaritmo della dimensione dell'array.

Il metodo dell'iterazione permette di scrivere la complessità temporale di Merge-Sort in funzione di n, la dimensione dell'array.

Il termine dominante nella complessità temporale di Merge-Sort è bn log2 n, che indica la crescita logaritmica della complessità rispetto alla dimensione dell'array.

Il termine bn log2 n indica che la complessità aumenta logaritmicamente con la dimensione dell'array.

Si riferisce a un algoritmo ricorsivo che divide l'input in sottoproblemi di dimensioni uguali ad ogni passo. Ad esempio, merge sort divide l'input in due metà ad ogni chiamata ricorsiva.

Un tipo di relazione di ricorrenza che descrive il comportamento di algoritmi come QuickSort, che suddividono l'input in due sottoproblemi di dimensioni non necessariamente uguali, ma che si avvicinano a un rapporto costante

Esprime il tempo di esecuzione di un algoritmo in funzione del numero di operazioni, in relazione alla dimensione dell'input.

Un limite superiore per la complessità temporale di un algoritmo, espresso nella notazione O (grande O). Indica il comportamento asintotico dell'algoritmo per dimensioni di input molto grandi. Ad esempio, l'algoritmo di merge sort ha una complessità temporale O(n log n), dove n è la dimensione dell'input.

indica che la complessità temporale dell'algoritmo è proporzionale alla dimensione dell'input moltiplicata per il logaritmo della dimensione dell'input. Ad esempio, l'algoritmo di merge sort ha una complessità temporale O(n log n).