Ako sa určuje časová zložitosť operácie získania prvku podľa indexu v zozname?

Časová zložitosť operácie získania prvku podľa indexu v zozname závisí od typu zoznamu:

• V políčku alebo zozname s podporou indexovania (napríklad List<T> v C#) je prístup podľa indexu operáciou s časovou zložitosťou O(1), pretože prvok je možné získať priamo podľa adresy.

• V prepojenom zozname (jednosmernom alebo obojstrannom) je prístup podľa indexu operáciou s časovou zložitosťou O(n), pretože na získanie prvku je potrebné prejsť zoznam od začiatku (alebo konca) až na požadovanú pozíciu.

V C# je trieda List<T> implementovaná na základe poľa, takže prístup podľa indexu je rýchly a má zložitosť O(1).