Lineær søketidskompleksitet

Lineært søk er sekvensielt søk. Denne metoden for å søke sjekker elementene på listen en-for-en, fra det første elementet. Når det ser den første forekomsten av elementet det leter etter, stopper søket. Elementet det leter etter kalles målet. Hvis elementet ikke er funnet, blir alle elementene i listen sjekket. Lineær søk er en veldig enkel søkealgoritme som enhver programmerer skal lære, enten offisielt eller intuitivt.

Tenk på følgende liste:

I J A C B G D H E F

For å se etter en, må programmet iterere listen 3 ganger. For å se etter G, må programmet iterere listen 6 ganger. For å se etter F, må programmet iterere listen 10 ganger. For å se etter K eller ethvert brev som ikke er på listen, må programmet iterere listen 10 ganger, og vil ikke finne en kamp.

Målet med denne artikkelen er å produsere tidskompleksiteten for lineær søk. Programmering gjøres i følgende C -diskusjon.

Lineær søkealgoritme

Algoritmen for lineær søk er rett frem. Anta at listen er en nullindeksert basert matrise. La variabelen som representerer hver indeks være i. La matrisen ha navnet a. Trinnene er som følger:

• • La jeg være 0.
  • Hvis en [i] er målet, blir verdien for jeg returnert og søket slutter vellykket.
  • Hvis en [i] ikke er målet, kan du øke I med 1 og gjenta forrige trinn.
  • Mens jeg er mindre enn N, der N er lengden på matrisen, fortsetter du å gjenta de to foregående trinnene i orden.
  • Fortsett på denne måten til målet enten er funnet eller ikke funnet.

Søket avsluttes med suksess når målet er funnet. Søket avsluttes uten hell når målet ikke er funnet. For en mislykket slutt blir alle N -elementene sjekket.

Tidskompleksitet

Tidskompleksitet er antall hovedoperasjoner for en viss kode for å fullføre oppgaven. Kontroller om målet samsvarer med et element er en operasjon. Det er dårligere tidskompleksitet, gjennomsnittlig tidskompleksitet og best case tidskompleksitet.

Verre-case tidskompleksitet

Det maksimale antallet operasjoner skjer når målet er på slutten av listen eller ikke er i listen i det hele tatt. Dette er verre tilfellet. Tidskompleksiteten er gitt som:

På)

Dette bruker Big-O-notasjonen. Big-O-notasjonen begynner med store bokstaver O, etterfulgt av parenteser. Inne i parentesene er uttrykket for antall operasjoner for å løse oppgaven.

Best case tidskompleksitet

Hvis det første elementet på listen er målet, er det bare en kontrolloperasjon som er nødvendig for søket. Det vil si at bare en operasjon er nødvendig for søket. Dette er den beste tidskompleksiteten. Det er skrevet som:

O (1)

Hvor 1 i parentesene betyr en operasjon.

Gjennomsnittlig tidskompleksitet

Gjennomsnittlig tidskompleksitet avhenger av sannsynlighetsfordelingen. Hvis hvert element kan være i noen posisjon, er det like sannsynlig at hvert element blir søkt. I denne situasjonen er gjennomsnittlig sakens tidskompleksitet gitt som:

O (n/2)

Programmering i c

Lineært søk er sannsynligvis det enkleste søket å skrive et program for. Bare følg algoritmen, som gjentas her, for enkel referanse:

• • La jeg være 0.
  • Hvis en [i] er målet, blir verdien for jeg returnert og søket slutter vellykket.
  • Hvis en [i] ikke er målet, kan du øke I med 1 og gjenta forrige trinn.
  • Mens jeg er mindre enn N, der N er lengden på matrisen, fortsetter du å gjenta de to foregående trinnene i orden.
  • Fortsett på denne måten til målet enten er funnet eller ikke funnet.

I hovedsak er programmet som følger:

#inkludere
int Linearsarch (char a [], int n, char t)
for (int i = 0; iif (t == a [i])
Returner jeg;

Det begynner med å inkludere stdio.H bibliotek som er ansvarlig for inngang og utgang. Etter det er det LinearSearch () -funksjonsdefinisjonen. Hovedkoden i funksjonsdefinisjonen er for-loop. For-loop skanner matrisen fra begynnelse til slutt, på jakt etter en kamp av målet. Hvis et mål blir funnet, returneres indeksen for det matchende elementet i matrisen. For å få det ordinære nummeret til indeksen for det matchede elementet, legg 1 til den nullbaserte indeksen.

En passende C hovedfunksjon for programmet ovenfor er som følger:

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);
retur 0;

Den første uttalelsen fra C -hovedfunksjonen erklærer antall elementer i den gitte matrisen. Etter det er det matrisen med navnet a. Det er ti tegn i matrisen. Erklæringen om matrisen begynner med "røye" og ikke "int". Derfra kalles den definerte LinearSearch () -funksjonen. Det første argumentet til funksjonssamtalen er matrisen. Det andre argumentet er antall elementer i matrisen. Det tredje argumentet er målet som er brevet hvis tilstedeværelse i matrisen er sjekket. Hvis den er til stede, returneres den nullbaserte indeksen. Hvis det ikke er til stede, blir ingenting returnert.

Neste uttalelse skriver ut hvilken som helst indeks som er returnert. For denne C hovedfunksjonen er 5 skrevet ut. Hvis 1 legges til 5, vil det være 6, som er ordinærindeksen.

Konklusjon

Tidskompleksiteten er gitt som:

På)

Dette bruker Big-O-notasjonen. Big-O-notasjonen begynner med store bokstaver O, etterfulgt av parenteser. Inne i parentesene er uttrykket for antall operasjoner for å løse oppgaven.

Hvis det første elementet på listen er målet, er det bare en kontrolloperasjon som er nødvendig for søket. Det vil si at bare en operasjon er nødvendig for søket. Dette er den beste tidskompleksiteten. Det er skrevet som:

O (1)

Hvor 1 i parentesene betyr en operasjon.

Gjennomsnittlig tidskompleksitet avhenger av sannsynlighetsfordelingen. Hvis hvert element kan være i noen posisjon, er hvert element like sannsynlig å bli søkt av denne algoritmen. I denne situasjonen er gjennomsnittlig sakens tidskompleksitet:

O (n/2)