Timpul constant și timpul constant amortizat sunt considerate efectiv echivalente?

Timpul constant amortizat poate fi considerat aproape întotdeauna echivalent cu timpul constant și fără a cunoaște specificul aplicației și tipul de utilizare pe care intenționați să îl faceți această coadă, cele mai multe șanse sunt că veți fi acoperit.

O listă de matrice are conceptul de capacitate , care este practic egal cu cea mai mare dimensiune / lungime / număr de articole care i sa cerut vreodată până acum. Deci, ceea ce se va întâmpla este că, la început, lista matricilor se va realoca în continuare pentru a-și crește capacitatea pe măsură ce adăugați elemente la ea, dar la un moment dat numărul mediu de articole adăugate pe unitate de timp se va potrivi inevitabil cu numărul mediu de articole eliminat pe unitate de timp, (altfel oricum ați rămâne fără memorie oricum), moment în care matricea se va opri din realocare și toate anexele vor fi îndeplinite în timp constant de O (1).

Cu toate acestea , rețineți că în mod implicit, eliminarea aleatorie dintr-o listă de matrice nu este O (1), este O (N), deoarece listele de matrice mută toate elementele după elementul eliminat cu o poziție în jos pentru a lua locul elementului eliminat . Pentru a obține O (1) va trebui să înlocuiți comportamentul implicit pentru a înlocui elementul eliminat cu o copie a ultimului element din lista de matrice, și apoi eliminați ultimul element, astfel încât niciun element să nu fie mutat. Dar atunci, dacă faceți asta, nu mai aveți exact o coadă.

Comentarii

• La naiba, un punct bun despre mutări; Nu ‘ nu am considerat asta. Și întrucât ‘ eliminăm elemente în mod aleatoriu, nu ‘ înseamnă că tehnic înseamnă ‘ Nu mai este o coadă în acest sens?
• Da, înseamnă că nu o tratați cu adevărat ca pe o coadă. Dar nu știu cum intenționați să găsiți elementele pe care să le eliminați. Dacă mecanismul tău de a le găsi se așteaptă ca acestea să fie prezente în coadă în ordinea în care au fost adăugate, atunci nu ai noroc.Dacă nu-ți pasă dacă ordinea articolelor devine zgârcită, atunci te simți bine.
• Așteptarea este ca RandomQueue să implementeze Queue și pentru metoda remove furnizată pentru a elimina aleatoriu, în loc să scoată capul, deci nu ar trebui să existe ‘ să nu fie orice mod de a vă baza pe o comandă specifică. Cred că, având în vedere natura aleatorie a acestuia, atunci, utilizatorul nu ar trebui să ‘ să se aștepte să păstreze orice ordine specifică. Am citat sarcina în întrebarea mea pentru clarificare. Vă mulțumim.
• Da, atunci se pare că veți fi bine dacă vă asigurați că eliminarea articolului se face așa cum am sugerat.
• Un ultim lucru dacă nu faceți ‘ t mind. ‘ m-am gândit mai mult și nu pare ‘ să nu pară ‘ Este posibil să aveți atât ” adevărat ” O (1) adăugiri, cât și ” adevărat ” O (1) eliminare aleatorie; ‘ va fi un compromis între 2. Aveți fie o structură alocată individual (cum ar fi o matrice) care oferă eliminare, dar nu un additon, fie o structură alocată în bucăți, cum ar fi un Linked- Listă care oferă completări, dar nu eliminare. E adevărat? Din nou, mulțumesc.

Întrebarea pare să ceară în mod specific timp constant și nu timp constant amortizat . Deci, în ceea ce privește întrebarea citată, nu, ele nu sunt efectiv aceleași *. Sunt totuși în aplicații din lumea reală?

Problema tipică cu constanta amortizată este că ocazional trebuie să plătiți datoria acumulată. Deci, în timp ce inserțiile sunt în general constante, uneori trebuie să suferiți cheltuielile generale pentru a reintroduce totul din nou atunci când este alocat un bloc nou.

În cazul în care diferența dintre timpul constant și timpul constant amortizat este relevantă pentru o aplicație, depinde dacă această viteză foarte lentă ocazională este acceptabilă. Pentru un număr foarte mare de domenii, acest lucru este în general în regulă. Mai ales dacă containerul are o dimensiune maximă eficientă (cum ar fi cache-uri, tampoane temporare, containere de lucru), puteți plăti în mod eficient costurile acestora o singură dată în timpul execuției.

Ca răspuns la aplicațiile critice, aceste perioade pot fi inacceptabile. Dacă vi se cere să îndepliniți o garanție scurtă, nu vă puteți baza pe un algoritm care îl va depăși ocazional. Am mai lucrat la astfel de proiecte, dar sunt extrem de rare.

Depinde și de cât de mare este acest cost. Vectorii tind să funcționeze bine, deoarece costul realocării lor este relativ scăzut. Cu toate acestea, dacă accesați harta hash, realocarea poate fi mult mai mare. Deși, din nou, pentru majoritatea aplicațiilor probabil că este bine, în special servere cu durată mai lungă de timp, cu o margine superioară pe articolele din container.

* Există totuși o problemă aici. Pentru a crea orice container de uz general să fie un timp constant pentru inserare, trebuie să rețină unul dintre cele două lucruri:

• Containerul trebuie să aibă o dimensiune maximă fixă; sau
• puteți presupune că alocarea de memorie a elementelor individuale este un timp constant .

Comentarii

• ” server de ficat ” pare o formulare ciudată de utilizat aici. Vrei să spui ” server live ” poate?

Depinde – dacă optimizați pentru randament sau pentru latență:

• Latență- sistemele sensibile au nevoie de performanțe consistente. Pentru un astfel de scenariu, trebuie să subliniem comportamentul cel mai rău al sistemului. Exemplele sunt sistemele soft în timp real, cum ar fi Jocurile care doresc să obțină un cadru de framer consistent sau serverele web care trebuie să trimită un răspuns într-un anumit interval de timp restrâns: pierderea ciclurilor CPU este mai bună decât întârzierea.
• Sistemele optimizate de transfer nu îți pasă standuri ocazionale, atâta timp cât cantitatea maximă de date poate fi procesată pe termen lung. Aici, suntem interesați în primul rând de performanța amortizată. Acesta este în general cazul cazurilor de restrângere a numerelor sau altor lucrări de procesare în serie.

Rețineți că un sistem poate avea componente diferite care trebuie clasificate diferit. De exemplu. un procesor de text modern ar avea un fir de interfață UI sensibil la latență, dar fire de procesare optimizate pentru alte sarcini, cum ar fi verificarea ortografică sau exporturile PDF.

De asemenea, complexitatea algoritmică de multe ori nu contează la fel de mult ca și noi gândiți-vă: atunci când o problemă este limitată la un anumit număr, atunci caracteristicile de performanță reale și măsurate sunt mai importante decât comportamentul „pentru n ” foarte mari.

Comentarii

• Din păcate, am foarte puține experiențe.Întrebarea se încheie cu: ” Operațiile add (x) și remove () dintr-o RandomQueue ar trebui să ruleze în timp constant per operație „.
• @Carcigenicate, cu excepția cazului în care știți cu certitudine că sistemul este sensibil la latență, utilizarea complexității amortizate pentru a selecta o structură de date ar trebui să fie absolut suficientă.
• Am impresia că ar putea fi un exercițiu de programare sau un test. Și cu siguranță nu una ușoară. Absolut adevărat că foarte rar contează.

Dacă vi se solicită un „timp constant amortizat” algoritm, algoritmul dvs. poate uneori să dureze mult. De exemplu, dacă utilizați std :: vector în C ++, un astfel de vector poate avea spațiu alocat pentru 10 obiecte, iar când alocați al 11-lea obiect, este alocat spațiu pentru 20 de obiecte, 10 obiecte sunt copiate și al 11-lea adăugat, care durează considerabil. Dar dacă adăugați un milion de obiecte, este posibil să aveți 999.980 de operații rapide și 20 de operații lente, timpul mediu fiind rapid.

Dacă vi se solicită un algoritm de „timp constant”, algoritmul dvs. trebuie să întotdeauna să fie rapid, pentru fiecare operație. Acest lucru ar fi important pentru sistemele în timp real în care este posibil să aveți nevoie de o garanție că fiecare operație este întotdeauna rapidă. „Timpul constant” nu este adesea necesar, dar este cu siguranță nu același cu „timpul constant amortizat”.