Qual é a complexidade temporal do acesso por índice numa lista?

A complexidade temporal de acesso por índice numa lista (std::list em C++) é O(n), onde n é o número do elemento.

Isto deve-se ao facto de std::list estar implementado como uma lista duplamente ligada, e para aceder a um elemento por índice é necessário percorrer sequencialmente desde o início ou o final da lista até ao elemento desejado.

Exemplo:

#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); // mover o iterador 3 posições à frente
    std::cout << "Elemento com índice " << index << ": " << *it << std::endl;
    return 0;
}

Para acesso rápido por índice, é melhor usar std::vector, onde o acesso por índice é O(1).