Complessità del tempo di ricerca lineare

La ricerca lineare è una ricerca sequenziale. Questo metodo di ricerca controlla gli elementi dell'elenco uno per uno, a partire dal primo elemento. Quando vede la prima occorrenza dell'elemento che sta cercando, la ricerca si interrompe. L'elemento che sta cercando è chiamato target. Se l'elemento non viene trovato, tutti gli elementi nell'elenco vengono controllati. La ricerca lineare è un algoritmo di ricerca molto semplice che ogni programmatore dovrebbe imparare, sia ufficialmente che intuitivo.

Considera il seguente elenco:

I j a c b g d h e f

Per cercare un, il programma deve iterare l'elenco 3 volte. Per cercare G, il programma deve iterare l'elenco 6 volte. Per cercare F, il programma deve iterare l'elenco 10 volte. Per cercare K o qualsiasi lettera che non si trova nell'elenco, il programma deve iterare l'elenco 10 volte e non troverà una corrispondenza.

Lo scopo di questo articolo è produrre la complessità temporale per la ricerca lineare. La programmazione viene eseguita nella seguente discussione C.

Algoritmo di ricerca lineare

L'algoritmo per la ricerca lineare è diretto. Supponiamo che l'elenco sia un array basato su zero indicizzato. Lascia che la variabile che rappresenti ogni indice sia io. Lascia che l'array abbia il nome a. I passi sono come segue:

• • Lascia che io sia 0.
  • Se un [i] è l'obiettivo, il valore per i viene restituito e la ricerca termina correttamente.
  • Se un [i] non è il bersaglio, aumenta i di 1 e ripeti il ​​passaggio precedente.
  • Mentre sono inferiore a n, dove n è la lunghezza dell'array, continua a ripetere i due passaggi precedenti per.
  • Continua in questo modo fino a quando il bersaglio non viene trovato o non si trova.

La ricerca termina correttamente quando viene trovato l'obiettivo. La ricerca termina senza successo quando il target non viene trovato. Per un finale senza successo, tutti gli elementi N vengono controllati.

Complessità temporale

La complessità del tempo è il numero di operazioni principali per un po 'di codice per completare il suo compito. Verifica se il target corrisponde a un elemento è un'operazione. C'è la complessità del tempo peggiore, la complessità del tempo medio e la complessità del tempo migliore.

Complessità del tempo peggiore

Il numero massimo di operazioni si verifica quando l'obiettivo è alla fine dell'elenco o non è affatto nell'elenco. Questo è il caso peggiore. La complessità del tempo peggiore è data come:

SU)

Questo usa la notazione Big-O. La notazione Big-O inizia con la maiuscola O, seguita da parentesi. All'interno delle parentesi c'è l'espressione per il numero di operazioni per risolvere l'attività.

Complessità del tempo migliore

Se il primo elemento dell'elenco è l'obiettivo, è necessaria solo un'operazione di controllo per la ricerca. Cioè, è necessaria solo un'operazione per la ricerca. Questa è la complessità del tempo migliore. È scritto come:

O (1)

Dove 1 tra parentesi significa un'operazione.

Complessità del tempo medio

La complessità del tempo medio dipende dalla distribuzione di probabilità. Se ogni elemento può essere in qualsiasi posizione, è altrettanto probabile che ogni elemento. In questa situazione, la complessità del tempo medio è data come:

O (n/2)

Programmazione in c

La ricerca lineare è probabilmente la ricerca più semplice per scrivere un programma per. Basta seguire l'algoritmo, che viene ripetuto qui, per un facile riferimento:

• • Lascia che io sia 0.
  • Se un [i] è l'obiettivo, il valore per i viene restituito e la ricerca termina correttamente.
  • Se un [i] non è il bersaglio, aumenta i di 1 e ripeti il ​​passaggio precedente.
  • Mentre sono inferiore a n, dove n è la lunghezza dell'array, continua a ripetere i due passaggi precedenti per.
  • Continua in questo modo fino a quando il bersaglio non viene trovato o non si trova.

In sostanza, il programma è il seguente:

#includere
int linearsearch (char a [], int n, char t)
per (int i = 0; iif (t == a [i])
ritorno i;

Inizia includendo lo stdio.Biblioteca H che è responsabile dell'ingresso e dell'output. Successivamente, c'è la definizione della funzione LineArsearch (). Il codice principale nella definizione della funzione è il per loop. Il per loop scansiona l'array dall'inizio alla fine, cercando una corrispondenza del bersaglio. Se viene trovato un target, l'indice per l'elemento corrispondente nell'array viene restituito. Al fine di ottenere il numero ordinale dell'indice dell'elemento abbinato, aggiungi 1 all'indice a base zero.

Una funzione principale C idonea per il programma di cui sopra è la seguente:

int main (int argc, char ** argv)

int n = 10;
char a [] = 'i', 'j', 'a', 'c', 'b', 'g', 'd', 'h', 'e', ​​'f';
int ret = linearsearch (a, n, 'g');
printf ("%i \ n", ret);
restituzione 0;

La prima dichiarazione della funzione principale C dichiara il numero di elementi nell'array dato. Successivamente, c'è l'array con il nome a. Ci sono dieci caratteri nell'array. La dichiarazione dell'array inizia con "char" e non "int". Da lì, la funzione definita linearsearch () è chiamata. Il primo argomento alla chiamata di funzione è l'array. Il secondo argomento è il numero di elementi nell'array. Il terzo argomento è l'obiettivo che è la lettera la cui presenza nell'array viene controllata. Se è presente, l'indice a base zero viene restituito. Se non è presente, nulla viene restituito.

L'istruzione successiva stampa qualsiasi indice restituito. Per questa funzione principale C, 5 è stampato. Se 1 viene aggiunto a 5, sarebbe 6, che è l'indice ordinale.

Conclusione

La complessità del tempo peggiore è data come:

SU)

Questo usa la notazione Big-O. La notazione Big-O inizia con la maiuscola O, seguita da parentesi. All'interno delle parentesi c'è l'espressione per il numero di operazioni per risolvere l'attività.

Se il primo elemento dell'elenco è l'obiettivo, è necessaria solo un'operazione di controllo per la ricerca. Cioè, è necessaria solo un'operazione per la ricerca. Questa è la complessità del tempo migliore. È scritto come:

O (1)

Dove 1 tra parentesi significa un'operazione.

La complessità del tempo medio dipende dalla distribuzione di probabilità. Se ogni elemento può essere in qualsiasi posizione, è altrettanto probabile che ogni elemento venga cercato da questo algoritmo. In questa situazione, la complessità del tempo medio è:

O (n/2)