Mi biztosítja a gyors hozzáférést egy tömb eleméhez a pozíciója szerint, és miért tekinthető ennek a műveletnek állandó időben történő végrehajtásnak?

A gyors hozzáférés egy tömb eleméhez a pozíciója alapján biztosított, mivel a tömb egy folyamatos memória blokkot valósít meg, ahol az elemek egymás után helyezkednek el.

Ez azt jelenti, hogy az i indexű elemhez való hozzáféréshez csak az címet kell kiszámítani:

A tömb kezdő címe + i * az elem mérete

A cím kiszámítása után az elemet közvetlenül el lehet érni anélkül, hogy az összes előző elemet végig kellene nézni.

Ezért az index szerinti hozzáférés művelete állandó időben — O(1), függetlenül a tömb méretétől.

Példa: Java vagy Kotlin esetén a tömbök úgy vannak kialakítva, hogy az array[i] közvetlen memória hozzáférés, nem pedig az elemek átjárása.