Betragtes konstant tid og afskrevet konstant tid effektivt som ækvivalente?

Amortiseret konstant tid kan næsten altid betragtes som ækvivalent med konstant tid og uden at kende specifikationen for din applikation og den anvendelsesform, du planlægger at gøre for at denne kø, mest sandsynlige er, at du bliver dækket.

En array-liste har begrebet capacity , som stort set svarer til den største størrelse / længde / antal varer, der har hidtil været krævet af det. Så hvad der vil ske er, at matrixlisten i starten fortsætter med at omfordele sig selv for at øge dens kapacitet, når du fortsætter med at tilføje varer til den, men på et tidspunkt vil det gennemsnitlige antal tilføjede varer pr. Tidsenhed uundgåeligt matche det gennemsnitlige antal varer fjernet pr. tidsenhed (ellers vil du til sidst løbe tør for hukommelse alligevel), på hvilket tidspunkt matrixen holder op med at omfordele sig selv, og alle tilføjelser vil blive mødt på konstant O (1).

Dog , husk på, at tilfældig fjernelse fra en matrixliste som standard ikke er O (1), det er O (N), fordi matrixlister flytter alle elementerne efter det fjernede element en position ned for at tage stedet for det fjernede element . For at opnå O (1) bliver du nødt til at tilsidesætte standardadfærden for at erstatte det fjernede element med en kopi af det sidste element i matrixlisten og derefter fjerne det sidste element, så ingen elementer flyttes. Men så hvis du gør det, har du ikke ligefrem en kø længere.

Kommentarer

• Damn, godt punkt på fjernelse; Jeg overvejede det ikke ‘. Og da vi ‘ tilfældigt fjerner elementer, betyder ‘ det ikke teknisk set ‘ Er det ikke længere en kø i den forstand?
• Ja, det betyder, at du ikke rigtig behandler det som en kø. Men jeg ved ikke, hvordan du planlægger at finde de emner, du vil fjerne. Hvis din mekanisme til at finde dem forventer, at de er til stede i køen i den rækkefølge, de blev tilføjet, så er du ude af lykke.Hvis du ikke er ligeglad med, om varernes rækkefølge bliver forvrænget, så har du det godt.
• Forventningen er, at min RandomQueue implementerer Queue interface og for den medfølgende remove metode til at fjerne tilfældigt i stedet for at poppe hovedet, så der skulle ikke være ‘ t være nogen måde at stole på en bestemt bestilling. Jeg tror i betragtning af den tilfældige karakter af det, at brugeren ikke ‘ ikke forventer, at den holder en bestemt rækkefølge. Jeg citerede opgaven i mit spørgsmål til afklaring. Tak.
• Ja da, det ser ud til, at det går fint, hvis du bare sørger for, at fjernelse af genstande sker som jeg foreslog.
• En sidste ting, hvis du ikke ‘ t sind. Jeg ‘ har overvejet det mere, og det ser det ikke ud ‘ ‘ s muligt at have både ” sand ” O (1) tilføjelser og ” sand ” O (1) tilfældig fjernelse; det ‘ vil være en afvejning mellem 2. Du har enten en enkeltallokeret struktur (som et array), der giver fjernelse, men ikke additon, eller en klumpallokeret struktur som en Linked- Liste, der giver tilføjelser, men ikke fjernelse. Er det sandt? Igen tak.

Spørgsmålet synes specifikt at bede om konstant tid og ikke en afskrevet konstant tid . Så med hensyn til det citerede spørgsmål, nej, de er faktisk ikke de samme *. Er de dog i applikationer i den virkelige verden?

Det typiske problem med amortiseret konstant er, at du lejlighedsvis skal betale den akkumulerede gæld. Så mens indsatser generelt er konstante, skal du nogle gange lide omkostningerne ved at genindsætte alt igen, når en ny blok tildeles.

Hvor forskellen mellem konstant tid og afskrevet konstant tid er relevant for en applikation, afhænger af, om denne lejlighedsvis meget langsomme hastighed er acceptabel. For et meget stort antal domæner er dette generelt okay. Især hvis containeren har en effektiv maksimal størrelse (som cacher, midlertidige buffere, arbejdscontainere), kan du effektivt betale de kun en gang under udførelsen.

Som reaktionskritiske applikationer kan disse tider være uacceptable. Hvis du skal overholde en kortvarig turnaround-garanti, kan du ikke stole på en algoritme, der lejlighedsvis vil overstige den. Jeg har arbejdet med sådanne projekter før, men de er meget sjældne.

Det afhænger også af, hvor høj denne pris faktisk er. Vektorer har en tendens til at klare sig godt, da deres omfordelingsomkostninger er relativt lave. Hvis du går til hash-kort, kan omfordelingen dog være meget højere. Skønt igen, for de fleste applikationer sandsynligvis fine, især længere levede servere med en øvre grænse på emnerne i containeren.

* Der er dog lidt af et problem her. For at lave en container til generelle formål være konstant tid til indsættelse, en af to ting skal holde:

• Containeren skal have en fast maksimal størrelse; eller
• du kan antage, at hukommelsestildeling af individuelle elementer er konstant tid .

Kommentarer

• ” leverserver ” virker en underlig formulering at bruge her. Mener du ” live server ” måske?

Det afhænger – af om du optimerer til gennemløb eller til latens:

• Latency- følsomme systemer har brug for ensartet ydeevne. For et sådant scenario skal vi understrege systemets værste tilfælde. Eksempler er bløde realtidssystemer, f.eks. s spil, der ønsker at opnå en ensartet framerate eller webservere, der skal sende et svar inden for en bestemt kort tidsramme: at spilde CPU-cyklusser er bedre end at være for sent.
• Gennemløbsoptimerede systemer er ligeglad med lejlighedsvise boder, så længe den maksimale mængde data kan behandles i det lange løb. Her er vi primært interesseret i amortiseret præstation. Dette er generelt tilfældet for antalknusning eller andre batchbehandlingsjob.

Bemærk, at et system kan have forskellige komponenter, der skal kategoriseres forskelligt. For eksempel. en moderne tekstbehandler ville have en latensfølsom UI-tråd, men gennemstrømningsoptimerede tråde til andre opgaver som stavekontrol eller PDF-eksport.

Også algoritmisk kompleksitet betyder ofte ikke så meget som vi måske tænk: Når et problem er afgrænset til et bestemt antal, så er faktiske og målte ydeevneegenskaber vigtigere end opførslen “for meget store n “.

Kommentarer

• Desværre har jeg meget lidt baggrund.Spørgsmålet slutter med: ” Funktionerne add (x) og remove () i en RandomQueue skal køre i konstant tid pr. Operation “.
• @Carcigenicate, medmindre du ved af en kendsgerning, at systemet er latensfølsomt, skal det være absolut tilstrækkeligt at bruge amortiseret kompleksitet til at vælge en datastruktur.
• Jeg har indtryk af, at dette måske er en programmeringsøvelse eller en test. Og bestemt ikke let. Helt sandt, at det meget sjældent betyder noget.

Hvis du bliver bedt om en “amortiseret konstant tid” algoritme, kan din algoritme undertiden tage lang tid. For eksempel, hvis du bruger std :: vector i C ++, kan en sådan vektor have tildelt plads til 10 objekter, og når du tildeler det 11. objekt, tildeles plads til 20 objekter, 10 objekter kopieres, og det 11. tilføjes, hvilket tager lang tid. Men hvis du tilføjer en million objekter, har du muligvis 999.980 hurtige og 20 langsomme operationer, hvor den gennemsnitlige tid er hurtig.

Hvis du bliver bedt om en “konstant tid” -algoritme, skal din algoritme altid være hurtig for hver enkelt operation. Det ville være vigtigt for realtidssystemer, hvor du muligvis har brug for en garanti for, at hver enkelt operation altid er hurtig. “Konstant tid” er meget ofte ikke nødvendigt, men det er bestemt ikke det samme som “afskrevet konstant tid”.