Az állandó idő és az amortizált állandó idő ténylegesen egyenértékűnek tekinthető-e?

Az amortizált állandó idő szinte mindig egyenértékűnek tekinthető az állandó idővel, anélkül, hogy ismerné az alkalmazás sajátosságait és a felhasználás típusát, amelyet tervez ebben a sorban a legvalószínűbb, hogy Ön lefed.

Egy tömblista a kapacitás fogalmával rendelkezik, amely alapvetően megegyezik a legnagyobb méret / hosszúság / elemszámmal, amely valaha is követelték tőle eddig. Tehát az fog történni, hogy az elején a tömblista folyamatosan átcsoportosítja magát, hogy növelje a kapacitását, miközben folyamatosan hozzáadja az elemeket, de egy bizonyos ponton az egységenként hozzáadott elemek átlagos száma elkerülhetetlenül meg fog egyezni az elemek átlagos számával időegységenként eltávolítva, (különben végül úgyis elfogyna a memóriája), ekkor a tömb abbahagyja önmagának átcsoportosítását, és az összes függelék O (1) állandó időpontjában teljesül.

Azonban , ne feledje, hogy alapértelmezés szerint a tömblista véletlenszerű eltávolítása nem O (1), hanem O (N), mert a tömblisták az eltávolított elem után az összes elemet egy pozícióval lefelé helyezik az eltávolított elem helyére. . Az O (1) elérése érdekében felül kell írnia az alapértelmezett viselkedést, amikor az eltávolított elemet a tömblista utolsó elemének másolatával helyettesíti, majd eltávolítja az utolsó elemet, így egyetlen elem sem kerül áthelyezésre. De akkor, ha ezt megteszed, már nincs pontosan sorod.

Megjegyzések

• A fenébe, jó pont az eltávolításokra; Nem vettem figyelembe ‘. És mivel ‘ véletlenszerűen eltávolítjuk az elemeket, nem ‘ t ez technikailag azt jelenti ‘ ilyen értelemben már nem áll sorban?
• Igen, ez azt jelenti, hogy nem igazán sorként kezeled. De nem tudom, hogyan tervezi megtalálni az eltávolítandó elemeket. Ha a megtalálásuk mechanizmusa azt várja, hogy abban a sorrendben legyenek jelen a sorban, amelyben felvették őket, akkor nincs szerencséje.Ha nem érdekel, hogy az elemek sorrendje elromlik, akkor minden rendben van.
• Az elvárás az, hogy RandomQueue megvalósítsa a Queue interfészhez, és a mellékelt remove metódushoz, hogy véletlenszerűen távolítsa el a fej felbukkanása helyett, ezért nem kellene ‘ semmilyen módon nem támaszkodhat egy adott megrendelésre. Azt gondolom, hogy annak véletlenszerű jellegéből adódóan a felhasználónak nem szabad div div ‘ elvárni, hogy bármilyen konkrét rendet tartson. Kérdésemben tisztázás céljából idéztem a megbízást. Köszönöm.
• Akkor úgy tűnik, hogy minden rendben lesz, ha csak megbizonyosodik arról, hogy az elem eltávolítása az általam javasolt módon történik.
• Még egy utolsó dolog, ha nem ‘ t elme. Én ‘ jobban átgondoltam, és nem tűnik úgy, hogy ‘ lehetséges, hogy mind ” true ” O (1) kiegészítés, mind pedig ” true ” O (1) véletlenszerű eltávolítás; Ez ‘ kompromisszumot jelent a 2. között. Önnek van egyenként allokált struktúrája (például egy tömb), amely eltávolítást ad, de nem ad hozzá, vagy olyan darabokra osztott struktúra, mint egy összekapcsolt- Az a lista, amely kiegészítéseket ad, de nem távolítja el. Igaz ez? Ismét köszönöm.

Úgy tűnik, hogy a kérdés kifejezetten állandó időt kér, és nem egy amortizált állandó idő . Tehát az idézett kérdés tekintetében nem, valójában nem azonosak *. Vannak-e valós alkalmazásokban?

Az amortizált állandó tipikus problémája az, hogy időnként meg kell fizetnie a felhalmozott adósságot. Tehát, míg a betétek általában állandóak, néha meg kell szenvednie azt, hogy mindent újból behelyezzen egy új blokk kiosztásakor.

Ahol az állandó idő és az amortizált állandó idő közötti különbség releváns egy alkalmazás számára, attól függ, hogy ez az alkalmi nagyon lassú sebesség elfogadható. Nagyon sok domainnél ez általában rendben van. Különösen, ha a tároló tényleges maximális mérete van (például gyorsítótárak, temp pufferek, működő tárolók), akkor a végrehajtás során csak egyszer fizetheti meg azok költségeit.

A kritikus alkalmazások válaszában ezek az idők elfogadhatatlanok lehetnek. Ha rövid időre meg kell felelnie az átfutási garanciának, akkor nem hivatkozhat olyan algoritmusra, amely időnként meghaladja ezt. Korábban dolgoztam ilyen projekteken, de ezek rendkívül ritkák.

Ez attól is függ, hogy ez a költség valójában mekkora. A vektorok általában jól teljesítenek, mivel az átcsoportosítás költsége viszonylag alacsony. Ha azonban hash térképre megy, akkor az átcsoportosítás sokkal nagyobb lehet. Bár megint a legtöbb alkalmazás valószínűleg rendben van, különösen a hosszabb élettartamú kiszolgálók felső korlátja van a tárolóban lévő elemeken.

* Itt azonban van egy kis probléma. Annak érdekében, hogy bármilyen általános célú tárolót készítsünk legyen állandó idő a beszúráshoz, a két dolog egyikének tartania kell:

• A tárolónak rögzített maximális méretűnek kell lennie; vagy
• feltételezheti, hogy az egyes elemek memória-allokációja állandó idő .

Megjegyzések

• ” májszerver ” furcsa kifejezésnek tűnik itt. Lehetséges, hogy ” élő szerverre gondolsz “?

Ez attól függ, hogy átviteli sebességre vagy késésre optimalizál:

• késés- érzékeny rendszereknek következetes teljesítményre van szükségük. Egy ilyen forgatókönyv esetén ki kell emelnünk a rendszer legrosszabb esetét. Ilyenek például a puha valós idejű rendszerek, például olyan játékok, amelyek állandó képkockasebességet akarnak elérni, vagy webszerverek, amelyeknek bizonyos szűk határidőn belül választ kell küldeniük: a CPU-ciklusok pazarlása jobb, mint késés.
• Az átviteli sebességre optimalizált rendszerek alkalmi elakadások, amennyiben a maximális adatmennyiség hosszú távon feldolgozható. Itt elsősorban az amortizált teljesítmény érdekel minket. Ez általában a számgörcsölés vagy más kötegelt feldolgozási feladatok esetében érvényesül.

Ne feledje, hogy egy rendszer különböző összetevőket tartalmazhat, amelyeket másként kell kategorizálni. Például. egy modern szövegfeldolgozó késleltetés-érzékeny felhasználói felületű szálat tartalmazna, de az áteresztőképességre optimalizált szálak más feladatokhoz, például a helyesírás-ellenőrzéshez vagy a PDF-exportáláshoz. gondolkodás: Ha egy probléma egy bizonyos számhoz van kötve, akkor a tényleges és a mért teljesítményjellemzők fontosabbak, mint a “nagyon nagy n ” viselkedés.

Megjegyzések

• Sajnos nagyon kevés háttérrel rendelkezem.A kérdés a következővel végződik: ” A RandomQueue add (x) és remove () műveleteinek állandó műveletenként kell futniuk “.
• @Carcigenicate, hacsak nem tudja pontosan, hogy a rendszer késleltetés-érzékeny-e, az amortizált összetettség felhasználásával az adatstruktúra kiválasztásához abszolút elegendőnek kell lennie.
• Úgy gondolom, hogy ez lehet programozási gyakorlat vagy teszt. És természetesen nem könnyű. Teljesen igaz, hogy nagyon ritkán számít.

Ha “amortizált állandó időt” kérnek tőled algoritmus, az algoritmus néha sokáig tarthat. Például, ha az std :: vector-ot használja a C ++ fájlban, akkor egy ilyen vektor 10 objektumhoz rendelhet helyet, és amikor a 11. objektumot lefoglalja, akkor 20 objektumot oszt ki a terület, 10 objektumot másol és a 11. hozzáadódik, jelentős időt vesz igénybe. De ha millió objektumot ad hozzá, 999 980 gyors és 20 lassú műveletet végezhet, az átlagos idő gyors.

Ha “állandó idő” algoritmust kérnek, akkor az algoritmusnak mindig gyorsnak kell lennie minden egyes művelethez. Ez fontos lenne a valós idejű rendszereknél, ahol szükség lehet garanciára arra, hogy minden egyes művelet mindig gyors. Az “állandó időre” gyakran nincs szükség, de határozottan nem megegyezik az “amortizált állandó idővel”.