Массив
Непрерывный блок памяти с доступом по индексу за константу.
Сигнатура
доступ O(1)Массив — это последовательность элементов одного типа, лежащих в памяти подряд. Адрес элемента вычисляется как база + индекс * размер, поэтому доступ по индексу занимает O(1).
Сложность: доступ и изменение по индексу — O(1); поиск значения — O(n); вставка/удаление в середину — O(n) из-за сдвига. Память: O(n).
Применяйте, когда размер известен заранее и нужен быстрый доступ по индексу.
a = [10, 20, 30, 40]
print(a[2]) # O(1) -> 30
a[2] = 99 # O(1)
print(30 in a) # O(n) линейный поиск