Временная сложность доступа по индексу в списке (std::list в C++) — O(n), где n — номер элемента.

Это связано с тем, что std::list реализован как двусвязный список, и для доступа к элементу по индексу требуется последовательный проход от начала или конца списка до нужного элемента.

Пример:

#include <list>
#include <iostream>

int main() {
    std::list<int> lst = {10, 20, 30, 40, 50};
    int index = 3;
    auto it = lst.begin();
    std::advance(it, index); // перемещаем итератор на 3 позиции вперед
    std::cout << "Элемент с индексом " << index << ": " << *it << std::endl;
    return 0;
}

Для быстрого доступа по индексу лучше использовать std::vector, где доступ по индексу — O(1).

Какова временная сложность доступа по индексу в списке (list)?