Articoli con tag complessità computazionale

Linguaggio C – Ricerca Interpolata

0
Implementazione in C, dell’algoritmo di RICERCA INTERPOLATA. Per array ordinati. A differenza di quella Binaria che divide in 2 l’array, la ricerca interpolata, sfruttando una formula (infatti funziona solo su array ordinati e con elementi equidistribuiti) cerca di avvicinarsi il più possibile [...]

Linguaggio C – Struttura dati: Code.

0
Una coda è una lista di tipo FIFO (First in, first out). Ovvero il primo atomo ad essere entrato nella coda è il primo che esce. Precedentemente abbiamo visto l’implementazione in linguaggio C della struttura dati dinamica, Pila. Qui di seguito, la definizione della struttura, e le varie funzioni [...]

Linguaggio C – Struttura dati lista collegata con puntatori.

1
RAPPRESENTAZIONE DINAMICA oppure RAPPRESENTAZIONE COLLEGATA con Puntatori di una Lista (Pila). La Struttura di tipo astratto Pila, coincide con quella più generica di Lista (anche se vedremo in seguito esistono anche altri tipo di liste chiamate CODE). La Pila è una lista di tipo LIFO (Last in [...]

Algoritmo di ordinamento: BubbleSort – C

0
L’algoritmo appartiene alla categoria: Ordinamento per interscambio. Effettua l’ordinamento di un array confrontando elementi adiacenti ed eventualmente scambiandoli. Poi effettua altre passate fin quando l’array è completamente ordinato. L’algoritmo fondamentalmente parte da destra (il secondo [...]

Linguaggio C – Struttura dati Lista Ordinata

0
In una lista ordinata, gli elementi sono inseriti in modo che la lista sia costituita da una sequenza ordinata di elementi. La struttura su cui andremo a lavorare sarà così composta: typedef int t_atomo;   typedef struct listaord { t_atomo info; struct listaord *prox; } t_listaord; Si tratta di [...]

Ricerca hash – Algoritmi di ricerca efficenti.

2
Tra i metodi di ricerca più efficenti vi è senza ombra di dubbio la Ricerca Hash. L’idea su cui si basa è quella che per trovare velocemente un elemento, basta sapere dove è stato messo. (Nei grandi Mainframe esistono delle vere e proprie tabelle hash, che rendono quasi immediata la ricerca), noi [...]

Algoritmo di ordinamento HeapSort, implementazione in C.

2
L’HeapSort è un algoritmo di ordinamento basato sui confronti, molto efficente. Complessità computazionale al più O(nlog_2n), al pari di QuickSort e MergeSort. L’algoritmo si compone di 3 funzioni essenzialmente: – La prima Rendi_heap, riceve in ingresso: l’array a[], la sua dimensione n, un certo [...]
Torna all'inizio