Quão rápido é possível encontrar um elemento ao procurar por índice em um segmento e em um mapa?

A busca de um elemento por índice numa fatia ([]) e por chave num mapa (map) em Go tem diferentes complexidades temporais.

• Fatia (slice): A busca por índice é um acesso direto ao elemento na memória pelo seu deslocamento.

  Complexidade temporal: O(1) – tempo constante. O acesso ao elemento não depende do tamanho da fatia.

  // Exemplo de acesso por índice numa fatia
  mySlice := []int{1, 2, 3, 4, 5}
  element := mySlice[2] // Acesso ao elemento com índice 2 (valor 3)
  

• Mapa (map): O mapa é implementado como uma tabela de dispersão. A busca por chave envolve calcular o valor hash da chave e depois acessar a célula correspondente na tabela de dispersão.

  Complexidade temporal média: O(1) – tempo constante. Com uma distribuição uniforme dos hashes, o acesso é rápido.

  Complexidade temporal no pior caso: O(n) – tempo linear. Isto pode acontecer em colisões fortes de hashes, quando é necessário percorrer uma lista ligada ou outra árvore na célula da tabela de dispersão. Na prática, isto é raro com uma boa função hash.

  // Exemplo de acesso por chave num mapa
  myMap := map[string]int{"one": 1, "two": 2, "three": 3}
  value, ok := myMap["two"] // Acesso ao valor com chave "two"
  // A variável 'value' conterá 2, 'ok' será true
  

Comparação:

Estrutura de dados	Acesso por	Complexidade temporal média	Complexidade temporal no pior caso
Fatia	Índice	O(1)	O(1)
Mapa	Chave (tabela de dispersão)	O(1)	O(n)

Assim, em casos típicos, a busca por índice numa fatia e por chave num mapa é muito rápida, com complexidade constante. No entanto, apenas o acesso por índice numa fatia garante O(1) em qualquer caso, enquanto que para o mapa existe um caso teórico (mas raro na prática) de O(n).