Aká je časová zložitosť operácie vektorového vloženia do dátových štruktúr a algoritmov?

Časová zložitosť operácie `insert` vo vektore závisí od , kde Vkladáte prvok.

Tu je porucha:

* vloženie na konci (pomocou `push_back` alebo ekvivalent): Toto je všeobecne o (1) - amortizovaný konštantný čas . „Amortizované“ znamená, že zatiaľ čo vektor občas musí prerozdeliť svoju základnú pamäť (ktorá trvá čas O (n)), vloženie väčšinou vloží jednoducho do nasledujúceho dostupného slotu. Počas mnohých inzercií je priemerný čas takmer konštantný.

* vkladanie do špecifickej polohy (pomocou `insert (pozícia iterátora, hodnota)` alebo ekvivalent): Toto je o (n) - lineárny čas . Tu je dôvod:

1. Nájdenie polohy: Ak je iterátor podaný priamo, nájdenie polohy v rámci existujúceho vektora je zvyčajne O (1). Ak však musíte * hľadať * bod vloženia (napr. Vloženie do triedeného poradia), samotný čas vyhľadávania môže byť O (n) alebo O (log n) v závislosti od použitého vyhľadávacieho algoritmu (lineárne vyhľadávanie alebo binárne vyhľadávanie). Ale presúvacia časť dominuje.

2. Posunie prvkov: Aby sa vytvoril priestor pre nový prvok, všetky prvky * Po * bod vloženia sa musí posunúť jedna pozícia doprava. V najhoršom prípade (vloženie na začiatku) musíte posunúť prvky `n`. V priemernom prípade (vkladanie do stredu) sa posúvate zhruba „n/2` prvky. V obidvoch prípadoch, posunutá operácia prispieva o (n) časová zložitosť.

Súhrnná tabuľka:

| Umiestnenie vkladania Časová zložitosť Vysvetlenie

|----------------------|-------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|

| Koniec (push_back) | O (1) (amortizované) Zvyčajne konštantný čas. Prerozdelenie môže byť občas potrebné, ale počas mnohých inzercií zostáva priemerný čas blízko konštanty. |

| Konkrétna pozícia O (n) | Vyžaduje sa posunutie všetkých prvkov po bode vloženia. Časová operácia dominuje časovej zložitosti. Poznámka:Ak je potrebné nájsť bod vloženia vyhľadávaním vo vektore, tento čas vyhľadávania by sa pridal k celkovej zložitosti. |

Dôležité úvahy:

* Repacition: Keď vektor dôjde z kapacity, musí prerozdeliť väčší blok pamäte a skopírovať všetky existujúce prvky do nového bloku. Táto operácia prerozdelenia je O (n). Vektory však často zdvojnásobujú svoju kapacitu zakaždým, keď sa prerozdelili, čím sa prerozdelenie dostatočne zriedkalo, aby sa náklady amortizovali v mnohých inzerciách.

* Vektorová implementácia: Špecifiká vektorových implementácií môžu mierne ovplyvniť výkon. Niektoré implementácie môžu napríklad používať sofistikovanejšie techniky správy pamäte.

Príklad (C ++):

`` CPP

#include

#include

int main () {

std ::vektor myVector ={1, 2, 3, 4, 5};

// vloženie na konci (amortizované o (1))

myVector.push_back (6);

std ::cout <<"po push_back:";

pre (int x:myVector) std ::cout < std ::cout <

// vloženie do špecifickej polohy (O (n))

MyVector.insert (myVector.Begin () + 2, 10); // Vložte 10 na index 2

Std ::cout <<"po vložení:";

pre (int x:myVector) std ::cout < std ::cout <

návrat 0;

}

`` `

Stručne povedané, pamätajte na * kde * vkladáte do vektora. „Push_back` je váš priateľ, ak sa potrebujete len pridať do konca. Ak potrebujete vložiť do stredu, zvážte dôsledky výkonnosti, najmä ak robíte veľa takýchto inzercií. Ak sú potrebné časté stredné inzercie, môžu byť vhodnejšie alternatívne dátové štruktúry, ako sú prepojené zoznamy alebo vyvážené stromy.

• Predchádzajúca strana: Aká je priestorová zložitosť štruktúry údajov o susednom zozname? 
• Ďalšia strana: No