Slå sammen sort tidskompleksitet

Heltalldivisjon av to

Heltalldivisjon er nødvendig når du gjør en sammenslåing.

Når et oddetall er delt med to, er det en resten av 1. For eksempel:

7/2 = 3 r 1

Heltalldivisjon betyr å ta hele tallet som svaret ditt og forlate 1.

Når et jevnt tall er delt med to, er det en resten av 0. For eksempel:

6/2 = 3 r 0

Heltalldivisjon betyr å ta hele tallet som svaret ditt og forlate 0.

I begge tilfeller blir hele antallet tatt og resten blir forlatt.

Målet med denne artikkelen er å bestemme tidskompleksiteten til Merge Sort, skrevet også som Fusjonsort. Sortering kan være stigende eller synke. Sortering i denne artikkelen refererer til å sortere stigende.

Slå sammen sorteringsalgoritme

Merge -sort er en skillelinje og erobrer sorteringsalgoritme. I denne algoritmen er den usorterte listen delt inn i to halvdeler ved bruk av heltalldivisjonen. Hver av halvdelene er videre delt inn i to halvdeler igjen ved hjelp av heltalldivisjonen. Denne divisjonen fortsetter til listen blir betraktet som enkelt separate elementer.

Fra venstre blir de påfølgende elementene deretter sammenkoblet på en sortert måte. De sammenkoblede elementene blir deretter sammenkoblet igjen i en sortert form. Denne gruppering av par fortsetter til hele listen er reformert og sortert.

Lineær og logaritmisk tidskompleksitet

Tenk på følgende kode på C -språket:

for (int i = 0; i<8; i++)
int k = i + 1;
printf ("%d", k);

printf ("\ n");

Utgangen er:

1 2 3 4 5 6 7 8

Koden er en for-loop (ignorerer utskriftserklæringen like etter for-loop). Den skriver ut heltallene fra 1 til 8, for totalt 8 tall. Innholdet i kroppen til for-loop er:

int k = i + 1;
printf ("%d", k);

Disse to uttalelsene blir betraktet som en hovedoperasjon i denne situasjonen. Det er 8 operasjoner. La n være 8. Dette er en lineær tidskompleksitet, og den er skrevet som følger:

På)

Hvor n er mulig maksimalt antall operasjoner. Dette er Big-O-notasjonen. Det begynner med O i store bokstaver og fulgt av parenteser. Inne i parentesene er maksimalt mulig antall operasjoner.

Tenk nå på følgende kode der av 8 tall, 3 tall skrives ut:

for (int i = 0; i<8; i++)
int k = i + 1;
printf ("%d", k);
if (k == 3) bryte;

printf ("\ n");

Utgangen er:

1 2 3

Koden er en for-loop (ignorerer utskriftserklæringen like etter for-loop). Det skriver ut heltallene fra 1 til 3 av 8 tall. Innholdet i kroppen til for-loop er:

int k = i + 1;
printf ("%d", k);
if (k == 3) bryte;

Fortsatt blir disse tre uttalelsene betraktet som en hovedoperasjon i denne situasjonen. Det er 3 operasjoner av 8.

Nå,

8 = 2³
=> 3 = log₂(8)

Så antallet hovedoperasjoner utført av forrige kode er 3 (av 8).

La n være 8. Dette er en logaritmisk tidskompleksitet, og den er skrevet som:

O (log₂n)

Hvor (logg₂ n) betyr 3 for forrige kode.

Det var 8 tall. Generelt sett, når antallet operasjoner for koden er mellom 2 og 5 av 8 og ikke bare 3, beskrives tidskompleksiteten som logg₂(n).

Eksempel på usortert og sortert liste

Et eksempel på usortert liste er som følger:

P V D Q S X T B

Det er åtte elementer på listen. Når denne listen er sortert, blir den:

B d p q s t v x

Teller antall hovedoperasjoner i flettesorteringen

Følgende liste:

P V D Q S X T B

brukes til å telle antall hovedoperasjoner i Merge Sort.

Heltalldivisjonen med to gir følgende resultat:

P V D Q S X T B

Dette er en operasjon. En annen deling av begge deler av to gir følgende resultat:

P V D Q S X T B

Dette er tre operasjoner så langt (ett pluss to). En annen divisjon av hver nye del av to gir følgende resultat:

P V D Q S X T B

Dette er syv operasjoner så langt (tre pluss fire). Listen over de åtte elementene regnes nå som åtte separate elementer med totalt syv operasjoner så langt. Den neste fasen er å parre mens du sorterer, som begynner fra venstre. Så neste resultat er:

P v d q s x b t

Det er to endringer i posisjon for det siste paret. To endringer er to operasjoner. Dette gjør totalt ni operasjoner så langt (syv pluss to).

Parring og sortering fortsetter, og begynner alltid fra venstre for å gi følgende resultat:

D p q v b s t x

Hver av disse to gruppene hadde fire endringer i posisjon, og utførte åtte operasjoner. Det er sytten operasjoner så langt (ni pluss åtte). Parring og sortering fortsetter og til slutt, for å gi følgende resultat:

B d p q s t v x

Det er syv endringer i posisjon her, og gjør syv operasjoner. Dette gjør tjuefire operasjoner (sytten pluss syv) for fullstendig sortering.

Tidskompleksitet for fusjonssortering

Den forrige tellingen (illustrasjon) brukes for å sitere tidskompleksiteten for sammenslåingen. Det er tjuefire operasjoner.

24 = 8 x 3

Det er:

24 = 8 x log₂(8)

Fordi log2 (8) er 3.

La 8 være n. Med det gis sammenslåingens tidskompleksitet av:

På.Logg₂n)

der prikken betyr multiplikasjon.

I praksis, av 8 elementer, er antall operasjoner omtrent 24 eller 24.

Konklusjon

Fusjonsortet er et bestemt skillelinje og erobrer sorteringsalgoritme. Det er en veldig effektiv sorteringsalgoritme. Tidskompleksiteten er veldig tilfredsstillende, sammenlignet med de andre sorteringsalgoritmene. Det er tidskompleksitet:

O (nlog₂n)

Merk: Antall operasjoner må ikke nødvendigvis være nøyaktig n.Log2n . Imidlertid bør det tilnærme det.

Koding Mergesort trenger rekursive funksjoner. Det er ikke så vanskelig å kode det når algoritmen er forstått. Koding av Merge Sort er en diskusjon for en annen gang.