Jak je určena časová složitost operace získání prvku podle indexu v seznamu?

Časová složitost operace získání prvku podle indexu v seznamu závisí na typu seznamu:

• U pole nebo seznamu s podporou indexování (například List<T> v C#) je přístup podle indexu operace s časovou složitostí O(1), protože prvek lze získat přímo podle adresy.

• U spojeného seznamu (jednosměrného nebo obousměrného) je přístup podle indexu operace s časovou složitostí O(n), protože k získání prvku je třeba projít seznam od začátku (nebo konce) až na požadovanou pozici.

V C# je třída List<T> implementována na základě pole, takže přístup podle indexu je rychlý a má složitost O(1).