Revision history [back]
 | 1 | initial version | posted 2014-10-08 16:24:33 +0100 |
Implementace fronty pomocí kruhového pole s $ O(1) $ vkládáním
Zdravím,
Chludil nás zaúkoloval, ať se doma koukneme, jak se implementuje fronta přes kruhové pole. Říkal myslím, že všechno tam může mít konstantní složitost a na přednáškách to bylo prezentovaný podobně.
Nějak ale nemůžu vymyslet, jak udělat konstantní insert. Přece když mi dojde kapacita a musím nafukovat, je potřeba všechny prvky z jedné strany posunout nakonec/začátek ne? Nebo je tam nějaký trik, jak to obejít?
A nebo se automaticky předpokládá amortizovaná složitost?
Předem díky za odpověď...
Implementace fronty pomocí kruhového pole s $ O(1) $ vkládáním
Zdravím,
Chludil nás zaúkoloval, ať se doma koukneme, jak se implementuje fronta přes kruhové pole. Říkal myslím, že všechno tam může mít konstantní složitost a na přednáškách to bylo prezentovaný podobně.
Nějak ale nemůžu vymyslet, jak udělat konstantní insert. Přece když mi dojde kapacita a musím nafukovat, je potřeba všechny prvky z jedné strany posunout nakonec/začátek ne? Nebo je tam nějaký trik, jak to obejít?
A nebo se automaticky předpokládá amortizovaná složitost?
Předem díky za odpověď...
