Middle
Qual é a complexidade das operações principais com coleções em Python?
sobes.tech IA
Resposta da IA
A complexidade das operações principais com coleções em Python (lista, dicionário, conjunto) pode ser representada na forma de tabela:
| Operação | Lista (list) |
Dicionário (dict) |
Conjunto (set) |
|---|---|---|---|
| Pesquisa de elemento | O(n) | O(1) | O(1) |
| Inserção de elemento | O(n) | O(1) | O(1) |
| Remoção de elemento | O(n) | O(1) | O(1) |
| Acesso por índice | O(1) | N/A | N/A |
| Iteração | O(n) | O(n) | O(n) |
| Comprimento da coleção | O(1) | O(1) | O(1) |
Explicações:
- O(1) - Complexidade constante: A operação é realizada em tempo fixo, independentemente do tamanho da coleção.
- O(n) - Complexidade linear: O tempo de execução da operação é proporcional ao tamanho da coleção.
- Busca, inserção e remoção em listas requerem deslocar elementos, o que leva tempo dependendo da posição do elemento e do tamanho da lista.
- Dicionários e conjuntos usam tabelas hash, o que garante em média tempo constante para busca, inserção e remoção. Em colisões de hash, essas operações podem piorar para O(n), mas na prática isso ocorre raramente.
- Acesso por índice em listas é O(1), pois os elementos são armazenados sequencialmente na memória.
- Iteração sobre todos os elementos da coleção sempre leva tempo proporcional à sua quantidade (O(n)).
- Obter o comprimento da coleção (com
len()) é O(1) para todos esses tipos de coleções, pois o comprimento é armazenado separadamente.
Exemplo de busca de elemento em uma lista:
# Busca de elemento em uma lista requer percorrê-la
my_list = [1, 2, 3, 4, 5]
if 3 in my_list:
pass # O(n) no pior caso
Exemplo de busca de elemento em um dicionário:
# Busca de elemento em um dicionário - O(1) em média
my_dict = {'a': 1, 'b': 2, 'c': 3}
if 'b' in my_dict:
pass # O(1) em média
Exemplo de adição de elemento ao final da lista:
# Adição de elemento ao final da lista - O(1) em média (amortizado)
my_list = [1, 2, 3]
my_list.append(4) # O(1) em média
Exemplo de adição de elemento ao início da lista:
# Adição de elemento ao início da lista - O(n)
my_list = [1, 2, 3]
my_list.insert(0, 0) # O(n)