Cik ātri var atrast elementu, ja meklējat pēc indeksa sējumā un kartē?

Go elementu meklēšana pēc indeksa sējumā ([]) un pēc atslēgas kartē (map) ir dažādas laika sarežģītības.

• Sējums (slice): Meklēšana pēc indeksa — tas ir tiešs piekļuves veids pie elementa atmiņā pēc tā novietojuma.

  Laika sarežģītība: O(1) — konstants laiks. Piekļuve elementam nav atkarīga no sējuma lieluma.

  // Piemērs piekļuvei pēc indeksa sējumā
  mySlice := []int{1, 2, 3, 4, 5}
  element := mySlice[2] // Piekļuve elementam ar indeksu 2 (vērtība 3)
  

• Kartē (map): Karte ir realizēta kā haštabula. Meklēšana pēc atslēgas — tas ir haša funkcijas aprēķins un pēc tam piekļuve atbilstošajai šūnai haštabulā.

  Vidējais laika sarežģītība: O(1) — konstants laiks. Ja haša funkcijas ir vienmērīgi sadalītas, piekļuve ir ātra.

  Sliktākajā gadījumā: O(n) — lineārs laiks. Tas var notikt stipru kolīziju gadījumos, kad ir jāapskata saistīts saraksts vai cits koks šūnā.

  // Piemērs piekļuvei pēc atslēgas kartē
  myMap := map[string]int{"one": 1, "two": 2, "three": 3}
  value, ok := myMap["two"] // Piekļuve vērtībai ar atslēgu "two"
  // Mainīgais 'value' saturēs 2, 'ok' būs true
  

Salīdzinājums:

Datu struktūra	Piekļuve pēc	Laika sarežģītība (vidējā)	Laika sarežģītība (sliktākajā gadījumā)
Sējums	Indeksam	O(1)	O(1)
Karte	Atslēgai (haštabula)	O(1)	O(n)

Tādējādi, parastajos gadījumos, meklēšana pēc indeksa sējumā un pēc atslēgas kartē notiek ļoti ātri un ar konstantu laika sarežģītību. Tomēr, tikai piekļuve pēc indeksa sējumā garantē O(1) jebkurā gadījumā, kamēr kartē ir teorētiskais (bet praksē reti sastopamais) sliktākais gadījums O(n).