Betraktes konstant tid og amortisert konstant tid som ekvivalente?

Amortisert konstant tid kan nesten alltid betraktes som ekvivalent med konstant tid, og uten å vite detaljene i applikasjonen din og hvilken type bruk du planlegger å gjøre for denne køen, er det mest sjanse for at du vil bli dekket.

En matriseliste har begrepet kapasitet , som i utgangspunktet er lik den største størrelsen / lengden / antall elementer som har noen gang blitt krevd av det så langt. Så, hva som vil skje er at i begynnelsen vil matriselisten fortsette å omdisponere seg selv for å øke kapasiteten når du fortsetter å legge til ting i den, men på et tidspunkt vil det gjennomsnittlige antall elementer lagt til per tidsenhet uunngåelig matche det gjennomsnittlige antall elementer fjernet per tidsenhet, (ellers vil du til slutt gå tom for minne uansett,) på hvilket tidspunkt matrisen vil slutte å omfordele seg selv, og alle appendene vil bli oppfylt på konstant tid av O (1).

Imidlertid , husk at som standard er tilfeldig fjerning fra en matriseliste ikke O (1), det er O (N), fordi matrixlister flytter alle elementene etter det fjernede elementet en posisjon ned for å ta stedet for det fjernede elementet . For å oppnå O (1) må du overstyre standardadferden for å erstatte det fjernede elementet med en kopi av det siste elementet i matriselisten, og deretter fjerne det siste elementet, slik at ingen elementer blir flyttet. Men så, hvis du gjør det, har du ikke akkurat kø lenger.

Kommentarer

• Damn, bra poeng med fjerning; Jeg ‘ t vurderte det ikke. Og siden vi ‘ fjerner elementer tilfeldig, betyr ikke ‘ det teknisk sett betyr det ‘ Er det ikke lenger en kø i så måte?
• Ja, det betyr at du egentlig ikke behandler det som en kø. Men jeg vet ikke hvordan du planlegger å finne varene du vil fjerne. Hvis mekanismen din for å finne dem forventer at de skal være til stede i køen i den rekkefølgen de ble lagt til, er du heldig.Hvis du ikke bryr deg om rekkefølgen på varene blir forvirret, så har du det bra.
• Forventningen er at RandomQueue skal implementere Queue grensesnitt, og for den medfølgende remove metoden for å tilfeldig fjerne i stedet for å sprute hodet, så det burde ikke være ‘ ikke være noen måte å stole på en bestemt bestilling. Jeg tror gitt den tilfeldige karakteren av det da, at brukeren ikke ‘ ikke forventer at den holder noen spesifikk rekkefølge. Jeg siterte oppgaven i spørsmålet mitt for avklaring. Takk.
• Ja da, det virker som om du vil ha det bra hvis du bare sørger for at fjerning av varen blir gjort slik jeg foreslo.
• En siste ting hvis du ikke ‘ t sinn. Jeg ‘ har tenkt meg mer om det, og det ser ikke ‘ ut ‘ s mulig å ha både » true » O (1) tillegg og » true » O (1) tilfeldig fjerning; det ‘ vil være en avveining mellom de 2. Du har enten en tildelt struktur (som en matrise) som gir fjerning, men ikke tillegg, eller en struktur som er tildelt klumper som en koblet- Liste som gir tillegg, men ikke fjerning. Er dette sant? Igjen, takk.

Spørsmålet ser ut til å spesifikt be om konstant tid, og ikke en amortisert konstant tid . Så med hensyn til det siterte spørsmålet, nei, de er ikke effektivt de samme *. Er de imidlertid i virkelige applikasjoner?

Det typiske problemet med amortisert konstant er at du av og til må betale den akkumulerte gjelden. Så mens innsatser generelt er konstante, må du noen ganger lide overhead for å sette inn alt igjen når en ny blokk er tildelt.

Hvor forskjellen mellom konstant tid og amortisert konstant tid er relevant for en applikasjon, avhenger av om denne sporadiske veldig treg hastigheten er akseptabel. For et veldig stort antall domener er dette generelt greit. Spesielt hvis beholderen har en effektiv maksimal størrelse (som cacher, midlertidige buffere, arbeidscontainere), kan du effektivt betale kostnadene bare én gang under kjøring.

Som svar kritiske applikasjoner kan disse tidene være uakseptable. Hvis du er pålagt å oppfylle en kort tidssikkerhetsgaranti, kan du ikke stole på en algoritme som noen ganger vil overstige det. Jeg har jobbet med slike prosjekter før, men de er ekstremt sjeldne.

Det kommer også an på hvor høy denne kostnaden faktisk er. Vektorer har en tendens til å prestere bra siden kostnadene for omdisponering er relativt lave. Hvis du går til hash-kart, kan omdisponeringen imidlertid være mye høyere. Skjønt igjen, for de fleste applikasjoner, antagelig bra, spesielt lengre levede servere med en øvre grense på elementene i beholderen.

* Det er imidlertid litt av et problem her. For å lage en generell container være konstant tid for innsetting en av to ting må holde:

• Beholderen må ha en fast maksimal størrelse; eller
• du kan anta at minnetildeling av individuelle elementer er konstant tid .

Kommentarer

• » leverserver » virker en merkelig formulering å bruke her. Mener du » live server » kanskje?

Det kommer an på – om du optimaliserer for gjennomstrømning eller for ventetid:

• Latens- følsomme systemer trenger jevn ytelse. For et slikt scenario må vi legge vekt på systemets dårligste oppførsel. Eksempler er myke sanntidssystemer som s spill som ønsker å oppnå en jevn framerate, eller webservere som må sende svar innen en viss kort tidsramme: å kaste bort CPU-sykluser er bedre enn å være sent.
• Gjennomstrømningsoptimaliserte systemer bryr seg ikke om sporadiske boder, så lenge den maksimale datamengden kan behandles i det lange løp. Her er vi først og fremst interessert i amortisert ytelse. Dette er vanligvis tilfelle for antall knusing eller andre batch-prosesseringsjobber.

Merk at ett system kan ha forskjellige komponenter som må kategoriseres forskjellig. F.eks. en moderne tekstbehandler vil ha en latenssensitiv UI-tråd, men gjennomstrømningsoptimaliserte tråder for andre oppgaver som stavekontroll eller PDF-eksport.

Algoritmisk kompleksitet har ofte ikke så stor betydning som vi kanskje tenk: Når et problem er avgrenset til et visst antall, så er faktiske og målte ytelsesegenskaper viktigere enn atferden “for veldig store n ”.

Kommentarer

• Dessverre har jeg veldig liten bakgrunn.Spørsmålet slutter med: » Add (x) og remove () -operasjonene i en RandomQueue skal kjøre i konstant tid per operasjon «.
• @Carcigenicate med mindre du vet for et faktum at systemet er latenssensitivt, bruk av amortisert kompleksitet for å velge en datastruktur bør være helt tilstrekkelig.
• Jeg har inntrykk av at dette kan være en programmeringsøvelse eller en test. Og absolutt ikke lett. Helt sant at det veldig sjelden betyr noe.

Hvis du blir bedt om en «amortisert konstant tid» algoritme, kan algoritmen din noen ganger ta lang tid. Hvis du for eksempel bruker std :: vector i C ++, kan en slik vektor ha tildelt plass til 10 objekter, og når du tildeler det 11. objektet, blir plass til 20 objekter tildelt, 10 objekter blir kopiert, og det 11. blir lagt til, som tar lang tid. Men hvis du legger til en million objekter, kan du ha 999.980 raske og 20 langsomme operasjoner, med gjennomsnittlig tid som er rask.

Hvis du blir bedt om en «konstant tid» -algoritme, må algoritmen din alltid være rask, for hver eneste operasjon. Det ville være viktig for sanntidssystemer der du kanskje trenger en garanti for at hver enkelt operasjon er alltid rask. «Konstant tid» er ofte ikke nødvendig, men det er definitivt ikke det samme som «amortisert konstant tid».