Kaip greitai galima rasti elementą, jei ieškote pagal indeksą skiltyje ir žemėlapyje?

Go elementų paieška pagal indeksą skaidinyje ([]) ir pagal raktą žemėlapyje (map) turi skirtingą laiko sudėtingumą.

• Skaidymas (slice): Paieška pagal indeksą — tai tiesioginis prieigos būdas prie elemento atmintyje pagal jo perkėlimą.

  Laiko sudėtingumas: O(1) — pastovus laikas. Prieiga prie elemento nepriklauso nuo skaidinio dydžio.

  // Pavyzdys prieigos pagal indeksą skaidinyje
  mySlice := []int{1, 2, 3, 4, 5}
  element := mySlice[2] // Prieiga prie elemento su indeksu 2 (reikšmė 3)
  

• Žemėlapis (map): Žemėlapis įgyvendintas kaip maišos lentelė. Paieška pagal raktą — tai raktų maišos reikšmės apskaičiavimas ir tada prieiga prie atitinkamos langelio maišos lentelėje.

  Vidutinė laiko sudėtingumas: O(1) — pastovus laikas. Jei maišos funkcijos paskirstytos tolygiai, prieiga yra greita.

  Blogiausias atvejis: O(n) — linijinis laikas. Tai gali įvykti stiprių kolizijų atvejais, kai reikia peržiūrėti susietą sąrašą arba kitą medį langelyje.

  // Pavyzdys prieigos pagal raktą žemėlapyje
  myMap := map[string]int{"one": 1, "two": 2, "three": 3}
  value, ok := myMap["two"] // Prieiga prie reikšmės pagal raktą "two"
  // Kintamasis 'value' turės 2, 'ok' bus true
  

Palyginimas:

Duomenų struktūra	Prieiga pagal	Laiko sudėtingumas (vidutinis)	Laiko sudėtingumas (blogiausias)
Skaidymas (slice)	Indeksas	O(1)	O(1)
Žemėlapis (map)	Raktas (maišos lentelė)	O(1)	O(n)

Taigi, įprastais atvejais, paieška pagal indeksą skaidinyje ir pagal raktą žemėlapyje vyksta labai greitai ir turi pastovų laiko sudėtingumą. Tačiau, tik prieiga pagal indeksą skaidinyje garantuoja O(1) bet kokiu atveju, o žemėlapis turi teorinį (bet praktikoje retą) blogiausio atvejo O(n).