Unisci la complessità del tempo di ordinazione
Divisione integer da due
La divisione integer è necessaria quando si esegue un tipo di unione.
Quando un numero dispari è diviso per due, c'è un resto di 1. Per esempio:
7 /2 = 3 R 1
Divisione intera significa prendere l'intero numero come risposta e abbandonare il 1.
Quando un numero pari è diviso per due, c'è un resto di 0. Per esempio:
6 /2 = 3 r 0
Divisione intera significa prendere l'intero numero come risposta e abbandonare lo 0.
In entrambi i casi, viene preso l'intero numero e il resto viene abbandonato.
Lo scopo di questo articolo è determinare la complessità temporale del tipo di unione, scritta anche come Mergesort. L'ordinamento può essere ascendente o scendendo. L'ordinamento in questo articolo si riferisce a ordinare ascendente.
Unisci algoritmo di ordinamento
L'ordinamento di unione è un algoritmo di smistamento di divisione e conquista. In questo algoritmo, l'elenco non desiderato è diviso in due metà usando la divisione interi. Ciascuna delle metà è ulteriormente divisa in due metà usando la divisione intera. Questa divisione continua fino a quando l'elenco non è considerato come singoli elementi separati.
A partire da sinistra, gli elementi consecutivi vengono quindi accoppiati in modo ordinato. Gli elementi accoppiati vengono quindi accoppiati di nuovo in una forma ordinata. Questo raggruppamento per coppie continua fino a quando l'intero elenco non viene riformato e ordinato.
Complessità del tempo lineare e logaritmico
Considera il seguente codice nella lingua C:
per (int i = 0; i<8; i++)
int k = i + 1;
printf ("%d", k);
printf ("\ n");
L'output è:
1 2 3 4 5 6 7 8
Il codice è un per loop (ignorando l'istruzione di stampa subito dopo il loop). Stampa i numeri interi da 1 a 8, per un totale di 8 numeri. Il contenuto del corpo del per loop è:
int k = i + 1;
printf ("%d", k);
Queste due affermazioni sono considerate come un'operazione principale in questa situazione. Ci sono 8 operazioni. Sia N 8. Questa è una complessità del tempo lineare ed è scritta come segue:
SU)
Dove n è il possibile numero massimo di operazioni. Questa è la notazione Big-O. Inizia con O in maiuscolo e seguito da parentesi. All'interno delle parentesi c'è il numero massimo possibile di operazioni.
Considera ora il seguente codice in cui vengono stampati 3 numeri, 3 numeri:
per (int i = 0; i<8; i++)
int k = i + 1;
printf ("%d", k);
if (k == 3) Break;
printf ("\ n");
L'output è:
1 2 3
Il codice è un per loop (ignorando l'istruzione di stampa subito dopo il loop). Stampa i numeri interi da 1 a 3 su 8 numeri. Il contenuto del corpo del per loop è:
int k = i + 1;
printf ("%d", k);
if (k == 3) Break;
Tuttavia, queste tre dichiarazioni sono considerate come un'operazione principale in questa situazione. Ci sono 3 operazioni su 8.
Ora,
8 = 23
=> 3 = log2(8)
Quindi, il numero di operazioni principali eseguite dal codice precedente è 3 (su 8).
Sia N 8. Questa è una complessità del tempo logaritmico ed è scritta come:
O (log2N)
Dove (registro2 n) significa 3 per il codice precedente.
C'erano 8 numeri. In generale, quando il numero di operazioni per il codice è compreso tra 2 e 5 su 8 e non solo 3, la complessità del tempo è descritta come log2(N).
Esempio di elenco non ordinato e ordinato
Un esempio di elenco non preventivo è il seguente:
P V D Q S X T B
Ci sono otto elementi nell'elenco. Quando questo elenco è risolto, diventa:
B D P Q S T V X
Contare il numero di operazioni principali nell'ordinamento di unione
Il seguente elenco:
P V D Q S X T B
viene utilizzato per contare il numero delle operazioni principali nell'ordinamento di unione.
La divisione interi di due dà il seguente risultato:
P V D Q S X T B
Questa è un'operazione. Un'altra divisione di entrambe le parti per due dà il seguente risultato:
P V D Q S X T B
Queste sono tre operazioni finora (una più due). Un'altra divisione di ogni nuova parte per due dà il seguente risultato:
P V D Q S X T B
Queste sono sette operazioni finora (tre più quattro). L'elenco degli otto elementi è ora considerato come otto elementi separati con un totale di sette operazioni finora. La fase successiva è quella di accoppiarsi durante l'ordinamento, a partire da sinistra. Quindi, il prossimo risultato è:
P v d q s x b t
Ci sono due modifiche in posizione per l'ultima coppia. Due modifiche sono due operazioni. Questo fa un totale di nove operazioni finora (sette più due).
L'abbinamento e l'ordinamento continuano, a partire sempre da sinistra per dare il seguente risultato:
D p q v b s t x
Ognuno di questi due gruppi ha avuto quattro modifiche in posizione, facendo otto operazioni. Finora ci sono diciassette operazioni (nove più otto). L'abbinamento e l'ordinamento continuano e infine, per dare il seguente risultato:
B D P Q S T V X
Ci sono sette cambiamenti in posizione qui, facendo sette operazioni. Questo fa ventiquattro operazioni (diciassette più sette) per il completo smistamento.
Complessità temporale per l'ordinamento di unione
Il conteggio precedente (illustrazione) viene utilizzato per citare la complessità temporale per il Mergesort. Ci sono ventiquattro operazioni.
24 = 8 x 3
Questo è:
24 = 8 x log2(8)
Perché log2 (8) è 3.
Lascia che 8 sia n. Con ciò, la complessità del tempo di Mergesort è data da:
SU.tronco d'albero2N)
dove il punto significa moltiplicazione.
In pratica, su 8 elementi, il numero di operazioni è di circa 24 o 24.
Conclusione
Il Mergesort è un particolare algoritmo di ordinamento di divisione e conquista. È un algoritmo di smistamento molto efficiente. La sua complessità temporale è molto soddisfacente, rispetto agli altri algoritmi di smistamento. La sua complessità temporale è:
O (Nlog2N)
Nota: il numero di operazioni non deve necessariamente essere esattamente n.log2n . Tuttavia, dovrebbe approssimare.
Coding Mergesort ha bisogno di funzioni ricorsive. Non è troppo difficile codificarlo una volta che l'algoritmo è stato compreso. Codificare il tipo di unione è una discussione per un'altra volta.