Koliko brzo se može pronaći element ako se traži po indeksu u preseku i u mapi?

Pretraživanje elementa po indeksu u odseku ([]) i po ključevi u mapi (map) u Go ima različite vremenske složenosti.

• Odsek (slice): Pretraživanje po indeksu je direktan pristup elementu u memoriji putem njegovog pomaka.

  Vremenska složenost: O(1) – konstantno vreme. Pristup elementu ne zavisi od veličine odseka.

  // Primer pristupa po indeksu u odseku
  mySlice := []int{1, 2, 3, 4, 5}
  element := mySlice[2] // Pristup elementu sa indeksom 2 (vrednost 3)
  

• Mapa (map): Mapa je implementirana kao hash tabela. Pretraživanje po ključevi uključuje izračunavanje hash vrednosti ključa i zatim pristup odgovarajućoj ćeliji u hash tabeli.

  Prosečna vremenska složenost: O(1) – konstantno vreme. Sa ravnomernom raspodelom hash-ova, pristup je brz.

  Najgori slučaj: O(n) – linearno vreme. Ovo se može desiti pri jakim kolizijama hash-ova, kada je potrebno pretražiti povezanu listu ili drugo stablo u ćeliji hash tabele. U praksi je ovo retko sa dobrom hash funkcijom.

  // Primer pristupa po ključevi u mapi
  myMap := map[string]int{"one": 1, "two": 2, "three": 3}
  value, ok := myMap["two"] // Pristup vrednosti po ključevi "two"
  // Promenljiva 'value' će sadržati 2, 'ok' će biti true
  

Poređenje:

Struktura podataka	Pristup putem	Prosečna vremenska složenost	Najgori slučaj vremenske složenosti
Odsek (slice)	Indeks	O(1)	O(1)
Mapa	Ključ (hash tabela)	O(1)	O(n)

Tako, u tipičnim slučajevima, pretraživanje po indeksu u odseku i po ključevi u mapi je veoma brzo, sa konstantnom složenošću. Međutim, samo pristup po indeksu u odseku garantuje O(1) u svakom slučaju, dok za mapu postoji teoretski (ali retko u praksi) slučaj O(n).