Koblet listetidskompleksitet
Enkelt koblet liste
Følgende diagram viser en enkelt koblet liste over tre elementer:
Hvert element har to deler. Den første delen har dataene. Den andre delen har en peker som peker på neste element. Det andre og tredje elementene ligner på den første. Det siste elementet har en nullpeker. Med den enkeltkoblede listen kan kryssing bare gå i en retning: den fremre retningen.
Elementene i en lenket liste blir ikke adressert av referanser (abonnement i firkantede parenteser), alt er likt. De får tilgang til av iteratorer (pekere). Når det.
Dobbeltkoblet liste
Følgende diagram viser en dobbelt koblet liste over tre elementer:
Her har hvert element tre deler. Den første delen har en peker som peker på det forrige elementet. Den andre delen har dataene. Den tredje delen har en peker som peker på neste element. Den første delen av det første elementet har en peker som peker på null. Den tredje delen av det siste elementet har en peker som peker på null. Med den dobbelt koblede listen kan kryssing gå i begge retninger: den fremre retningen eller omvendt retning.
Elementene i en lenket liste blir ikke adressert av referanser (abonnement i firkantede parenteser). De får tilgang til av iteratorer (pekere). Når det gjelder en dobbelt koblet liste, kan iteratoren bevege seg i begge retninger, men må starte i hver ende. Bevegelse kan ikke starte offisielt fra listen.
Målet med denne artikkelen er å bestemme hva som kalles tidskompleksiteten for den koblede listen.
Tidskompleksitet generelt
Tidskompleksitet er den relative kjøretiden til en viss kode. Tidskompleksitet kan også sees på som antall hovedoperasjoner i koden.
Konstant tid
En hovedoperasjon som innsetting eller sletting sies å ha en tidskompleksitet av konstant tid fordi handlingen kan sees på som å oppstå en gang. Det er skrevet som:
O (1)
der 1 betyr konstant tid eller handling som oppstår en gang. Dette bruker Big-O-notasjonen som begynner med O i store bokstaver etterfulgt av parenteser. Inne i parentesene er antallet hovedoperasjoner for oppgaven.
Lineær tid
Lese en matrise fra begynnelsen- det ene elementet etter det andre på jakt etter et bestemt element- blir referert til som et lineært søk.
Elementet som er sett etter, kan finnes et sted på midten og søket ville stoppe. Dette er fremdeles et lineært søk. Tidskompleksiteten for lineær søk er skrevet som:
På)
hvor n er maksimalt mulig antall operasjoner.
Koblet liste hovedoperasjoner
Søker
For enkeltkoblet liste, for å gå fra det ene elementet til det neste, må koden bruke det nåværende elementets peker, som peker på neste element. Dette er ikke tilfelle med matriser. For dobbeltkoblet liste, for å gå fra det ene elementet til det neste, må koden bruke det nåværende elementets peker som peker på neste element. Dette er ikke tilfelle med matriser. For dobbeltkoblet liste, for å gå fra ett element til det forrige, må koden bruke det nåværende elementets peker som peker på det forrige elementet. Dette er ikke tilfelle med matriser.
Sletting
Når et nåværende element blir slettet, må pekeren til det forrige elementet som pekte på det, gjøres for å peke på neste element. Deretter må pekeren til det neste elementet det pekte på det, gjøres for å peke på det forrige elementet.
Innsetting
Når det nåværende elementet settes inn, må pekeren til det forrige elementet som pekte på neste element, gjøres for å peke på det nåværende elementet. Pekeren til det neste elementet som pekte på det forrige elementet, må gjøres for å peke på det nåværende elementet.
Frontpekeren til det nåværende elementet må gjøres for å peke på det nye neste elementet. Bakpekeren til det nåværende elementet må gjøres for å peke på det nye tidligere elementet.
Tidskompleksitet for koblet liste
Når du snakker om tidskompleksitet for en lenket liste, er det tidskompleksiteten for søk, sett inn og slett som snakkes om. Det er ikke tidskompleksiteten for å bygge den koblede listen som snakkes om. Tidskompleksitet for å bygge en koblet liste er et annet problem.
Søker
For at en enkelt koblet liste skal søke etter et bestemt element (data), må søkekoden skanne listen- elementet etter element- fra begynnelsen. For at en dobbelt koblet liste skal søke etter et bestemt element, må søkekoden skanne listen- elementet etter element- fra begynnelsen. Eller skann listen, element etter element, fra slutten. Søketidskompleksiteten for en lenket liste (enkeltvis eller dobbelt) er:
På)
hvor n er antall elementer i listen. Det spiller ingen rolle om elementet ble funnet, et sted på listen.
Innsetting
Innføring anses som en hovedoperasjon. For å sette inn et element i en koblet liste, må søket finne sted, for å komme frem til stillingen, for innsetting. Tidskompleksiteten for å søke er O (n). Tidskompleksiteten for virkningen av å sette inn er O (1). Så tidskompleksiteten for innsetting i en koblet liste er O (n + 1). For enkelhets skyld er tidskompleksiteten for innsetting av et element, til en koblet liste, skrevet som:
På)
Sletting
Sletting anses som en hovedoperasjon. For å slette et element i en koblet liste, må søket finne sted, for å komme frem til stillingen for sletting. Tidskompleksiteten for å søke er O (n). Tidskompleksiteten for å slette virkningen, er O (1). Så tidskompleksiteten for sletting i en koblet liste er O (n + 1). For enkelhets skyld er tidskompleksiteten for sletting av et element, av en lenket liste, skrevet som:
På)
Bygge en koblet liste i C
For å bygge en dobbelt koblet liste i C, bruk struct -objektet. Det første datamedlemmet skal ha en peker som peker på forrige struktur. Det tredje datamedlemmet skal ha en peker som peker på neste struktur. Det midterste datamedlemmet skal ha dataene. Det første datamedlemmet i den første strukturen skal peke på null. Det tredje datamedlemmet av den siste strukturen skal også peke på null.
I tilfelle av enkeltkoblet liste, utelater du det første datamedlemmet.
Konklusjon
Tidskompleksiteten for å søke i en lenket liste er:
På)
For enkelhets skyld er tidskompleksiteten for å sette inn et element i en koblet liste:
På)
og ikke o (1).
For enkelhets skyld er tidskompleksiteten for sletting av et element, av en lenket liste:
På)
og ikke o (1).