Algoritmi e strutture dati e complessità

Algoritmi e Strutture dati Costo Tipo di Algoritmo Caso migliore Caso peggiore In-place Stabile Divide et impera Note Insetion Sort O(n) (n2) SI SI NO Il caso peggiore è quando l'array è ordinato in modo decrescente . Il caso migliore quando l'array è gia rodinato Non esiste una distinzione tra caso migliore e caso peggiore va bene qualsiasi input Causa due cicli for ha la stessa complessità nei diversi casi Qualsiasi si l'input va bene Procedura di fusione del merge-sort Il caso migliore è quando il vettore in input deve essere una heap. Il caso peggiore quando il vettore è una heap all'incontrario. Se implementato con un ciclo "for" diventa inplace Il caso migliore è quando le chiamate al nodo rispetta le proprietà della heap. Il caso peggiore quando devo conmtrollare tutti i nodi fino in fondo. Se il pivot viene preso come min o come max, oppure il vettore è gia ordinato in maniera decrescente, si è nel caso peggiore; se invece il pivot viene preso a metà dell'array dove n è dispari, si è nel caso migliore Selection Sort O(n2) O(n2) SI SI NO Bubble Sort Merge Sort Merge O(n2) (n log n) (n) O(n2) (n log n) (n) SI NO NO SI SI SI NO SI Heap Sort (n log n) (n log n) NO NO NO Heapify (1) (log n) NO NO NO Build Heap (n) (n) NO NO NO Quick Sort O(n log n) (n2) NO NO SI Partition (n) (n) SI NO Algoritmi e Strutture dati Costo Tipo di Algoritmo Caso migliore Caso peggiore In-place Stabile Divide et impera Note Counting Sort (non basato sul confronto) O(n) O(k+n) = O(n) oppure (n) NO SI NO K è una costante che limita superiormante la funzione, in quanto bisogna considerare n interi compresi tra 0 e k; k deve essere fissata a priori Devono essere numeri al massimo di k Digit. K è una costante che limita superiormante la funzione e il numero dei decimali presi in considerazione (Digit) Il caso migliore è quando i numeri sono disposti più o meno alla stessa distanza. Il caso peggiore tutti i numeri cadono in un solo bucket Divido A in blocchi di 5 elementi; cerco il mediano di ogni blocco; scrivo il vettore dei mediani Radix Sort (usa Counting Sort, non basato sul confronto) O(n) Dipende Dipende O(dk+n) = dall'algoritmo dall'algoritmo O(n) oppure di di (n) ordinamento ordinamento che uso che uso (SI) NO Bucket Sort (usa numeri compresi tra 0 e 1, non basato sul confronto) O(n) O(n2) NO SI NO Select Randomized Select Stack Empty Push Pop Dequeue Eneque List Search List Insert List Delete In-Order tree walk Pre-Order tree walk (n) O(n) (n) O(n2) O(1) O(1) (1) (1) (l) (1) (l) O(n) O(n) NO NO SI dove l è la lunghezza della lista dove l è la lunghezza della lista Stampa in ordine : Tree-left(Root), Root e Tree-right(Root) Stampa in ordine : Root, Tree-left(Root) e Tree-right(Root) Algoritmi e Strutture dati Costo Tipo di Algoritmo Caso migliore Caso peggiore O(n) In-place Stabile Divide et impera Note Stampa in ordine : Tree-left(Root), Tree-right(Root) e Root Con il termine h si intende l'altezza dell'albero in esame (h= log2 n) Con il termine h si intende l'a Continua »