Jak szybko można znaleźć element, szukając po indeksie w fragmencie i w mapie?

Wyszukiwanie elementu według indeksu w zakresie ([]) i według klucza w mapie (map) w Go ma różne złożoności czasowe.

• Szczątka (slice): Wyszukiwanie po indeksie to bezpośredni dostęp do elementu w pamięci według przesunięcia.

  Złożoność czasowa: O(1) – czas stały. Dostęp do elementu nie zależy od rozmiaru zakresu.

  // Przykład dostępu po indeksie w zakresie
  mySlice := []int{1, 2, 3, 4, 5}
  element := mySlice[2] // Dostęp do elementu z indeksem 2 (wartość 3)
  

• Mapa (map): Mapa jest zaimplementowana jako tabela haszująca. Wyszukiwanie po kluczu wymaga obliczenia wartości hash klucza, a następnie dostępu do odpowiedniej komórki w tabeli.

  Średnia złożoność czasowa: O(1) – czas stały. Przy równomiernym rozkładzie hashy dostęp jest szybki.

  Najgorsza złożoność czasowa: O(n) – czas liniowy. Może się to zdarzyć przy silnych kolizjach hashy, gdy trzeba przeszukać powiązaną listę lub inne drzewo w komórce tabeli.

  // Przykład dostępu po kluczu w mapie
  myMap := map[string]int{"one": 1, "two": 2, "three": 3}
  value, ok := myMap["two"] // Dostęp do wartości po kluczu "two"
  // Zmienna 'value' będzie zawierać 2, 'ok' będzie true
  

Porównanie:

Struktura danych	Dostęp przez	Średnia złożoność czasowa	Najgorsza złożoność czasowa
Szczątka	Indeks	O(1)	O(1)
Mapa	Klucz (tabela haszująca)	O(1)	O(n)

W ten sposób, w typowych przypadkach, wyszukiwanie po indeksie w zakresie i po kluczu w mapie jest bardzo szybkie, z czasem stałym. Jednak dostęp po indeksie w zakresie gwarantuje O(1) w każdym przypadku, podczas gdy dla mapy istnieje teoretyczny (choć rzadki w praktyce) przypadek O(n).