Ինչքան արագ կարելի է գտնել տարր, եթե որոնում եք ըստ ինդեքսի կտորում և քարտեզում (մապ)?

Գտնվելը տարր ըստ ինդեքսի կտորում ([]) և ըստ բանալիի քարտեզում (map) Go-ում ունի տարբեր ժամանակային բարդություն:

• Կտոր (slice): Գտնվելը ըստ ինդեքսի — դա ուղղակի մուտք է հիշողության մեջ ըստ նրա տեղաշարժի:

  Ժամանակային բարդություն: O(1) — կայուն ժամանակ: Մուտքը տարրին կախված չէ կտորի չափից:

  // Օրինակ՝ մուտք ըստ ինդեքսի կտորում
  mySlice := []int{1, 2, 3, 4, 5}
  element := mySlice[2] // Մուտք ինդեքսով 2 (արժեքը 3)
  

• Քարտեզ (map): Քարտեզը իրականացվում է որպես հեշ-թաբլիթ։ Գտնվելը ըստ բանալի — դա հաշվել է բանալիի հեշ-արժեքը և ապա մուտք գործել համապատասխան բջիջը հեշ-թաբլիթում:

  Միջին ժամանակային բարդություն: O(1) — կայուն ժամանակ: Եթե հեշերը հավասարաչափ տարածված լինեն, մուտքը արագ է:

  Ամենավատ դեպքի ժամանակային բարդություն: O(n) — գծային ժամանակ: Դա կարող է տեղի ունենալ հեշ-կոլիզիաների դեպքում, երբ անհրաժեշտ է դիտել կապված ցանկը կամ այլ ծառը հեշ-թաբլիթում։ Իրականում դա հազվադեպ է, լավ հեշ-ֆունկցիայի դեպքում:

  // Օրինակ՝ մուտք ըստ բանալիի քարտեզում
  myMap := map[string]int{"one": 1, "two": 2, "three": 3}
  value, ok := myMap["two"] // Մուտք արժեքի համար "two"
  // Փոփոխական 'value' կպահպանի 2-ը, 'ok' կլինի true
  

Համեմատություն:

Տվյալների կառուցվածք	Մուտք ըստ	Ժամանակային բարդություն (միջին)	Ժամանակային բարդություն (ամենավատ դեպքում)
Կտոր	Ինդեքսին	O(1)	O(1)
Քարտեզ	Բանալի (Հեշ-թաբլիթ)	O(1)	O(n)

Այսպիսով, սովորական դեպքերում, ըստ ինդեքսի որոնումը կտորում և ըստ բանալիի որոնումը քարտեզում շատ արագ են և ունեն կայուն ժամանակային բարդություն։ Սակայն, միայն ըստ ինդեքսի մուտքը կտորում երաշխավորում է O(1) ցանկացած դեպքում, իսկ քարտեզի համար կա տեսական (բայց հազվադեպ գործնականում) ամենավատ դեպքի O(n):