Junior
Aká je asymptotická zložitosť operácií s prvkami v zozname?
sobes.tech AI
Odpoveď od AI
Závisí od typu zoznamu a operácie.
Obvykle sa zvažujú nasledujúce typy zoznamov:
- Jednosmerný spojený zoznam
- Dvosmerný spojený zoznam
- Pole (ako špeciálny prípad zoznamu)
Operácie:
- Prístup podľa indexu
- Vloženie
- Vymazanie
- Vyhľadanie hodnoty
| Operácia | Jednosmerný spojený zoznam | Dvosmerný spojený zoznam | Pole |
|---|---|---|---|
| Prístup podľa indexu | O(n) | O(n) | O(1) |
| Vloženie | O(1) (na začiatku) | O(1) (na začiatku/konci) | O(n) |
| Vymazanie | O(n) | O(n) | O(n) |
| Vyhľadanie hodnoty | O(n) | O(n) | O(n) |
Vysvetlenie:
- O(1) (Konštantný čas): Operácia trvá pevný čas, nezávisle od veľkosti zoznamu. Napríklad, prístup k prvku podľa indexu v poli.
- O(n) (Lineárny čas): Čas vykonania operácie je úmerný veľkosti zoznamu. Napríklad, vyhľadávanie prvku v nesortovanom zozname.
- O(log n) (Logaritmický čas): Čas vykonania rastie logaritmicky s veľkosťou zoznamu. Často sa vyskytuje pri práci so zoradenými dátami (napríklad binárne vyhľadávanie).
Detaily:
- V jednosmernom spojenom zozname: Vloženie na začiatok - O(1). Vloženie na koniec alebo vloženie/odstránenie podľa indexu vyžaduje prejsť zoznam až k požadovanému prvku, čo dáva O(n).
- V dvosmernom spojenom zozname: Vloženie na začiatok a koniec - O(1). Vloženie/odstránenie na určenej pozícii - O(1), ale vyhľadanie tohto uzla podľa hodnoty alebo indexu - O(n).
- V poli: Prístup podľa indexu - O(1). Vloženie alebo odstránenie uprostred poľa vyžaduje posun prvkov, čo dáva O(n). Vloženie/odstránenie na konci, ak je rezervovaná kapacita (napríklad v
std::vectors určitým kapacitou), môže byť priemerne O(1), ale v najhoršom prípade (reallocácia) O(n).