Kā noteikt operācijas laika sarežģītību, ievietojot elementu vārdnīcu pārstāvošas datu struktūras vidū?

Elementa ievietošana datu struktūrā, kas pārstāv vārdnīcu, ir atkarīga no konkrētās vārdnīcas īstenošanas. Standarta vārdnīcās (piemēram, Dictionary Swift vai NSDictionary Objective-C) elementi nav sakārtoti ar indeksu, tāpēc jēdziens "ievietot vidū" nav tieši piemērojams.

Ja runa ir par datu struktūru, kas glabā pārus atslēga-vērtība kārtotā veidā (piemēram, pāru masīvs), tad ievietošana vidū prasa pārvietot visus turpmākos elementus, kas rada laika sarežģītību O(n), kur n ir elementu skaits pēc ievietošanas pozīcijas.

Hash tabulās (pamatā vārdnīcām) ievietošana parasti notiek amortizētā laikā O(1), bet bez jēdziena "vidus".

Tātad, ja datu struktūra ir sakārtota un realizēta kā masīvs, ievietošana vidū ir O(n). Ja tā ir hash tabula, ievietošana ir O(1), bet jēdziens "vidus" nav piemērojams.