Împarte problema în două
O(log n) înseamnă timp logaritmic: fiecare pas taie în jumătate munca rămasă. Pentru că înjumătățirea micșorează numerele atât de repede, dublarea datelor de intrare adaugă doar un singur pas în plus.
16 elemente au nevoie de 4 înjumătățiri, 32 de elemente au nevoie de 5, un milion de elemente aproximativ 20, un miliard aproximativ 30. De aceea algoritmii logaritmici par instantanei chiar și pe date uriașe.
Exemplul clasic este căutarea binară — dar ea funcționează doar pe date sortate. Înjumătățirea are nevoie de o ordine ca să știe ce jumătate să arunce.
O buclă care înjumătățește
Cel mai simplu mod de a vedea O(log n) este o buclă care împarte n la 2 până ajunge la 1. Numărul de runde este logaritmul lui n: pentru n = 16 bucla rulează de 4 ori, pentru că 2 · 2 · 2 · 2 = 16.
Înjumătățire până rămâne unu
16 devine 8, 4, 2, 1 — patru pași. Dublarea lui n la 32 ar adăuga doar încă un pas.
Ieșire: program Go și rezultatul capturat
package main
import "fmt"
func main() {
n := 16
steps := 0
for n > 1 {
n = n / 2
steps++
fmt.Println("n este acum", n)
}
fmt.Println("16 a devenit 1 în", steps, "pași")
}
Căutarea binară
Căutarea binară găsește o valoare într-un slice sortat verificând mereu elementul din mijloc. Dacă mijlocul este prea mic, toată jumătatea stângă este aruncată; dacă este prea mare, jumătatea dreaptă. Fiecare verificare înjumătățește intervalul de căutare.
Două repere, lo și hi, țin intervalul curent. Bucla se termină când valoarea este găsită sau când intervalul este gol.
Go oferă acest lucru și gata făcut: slices.BinarySearch() întoarce indexul și un bool. Când valoarea lipsește, indexul este poziția în care ar fi inserată.
Căutarea binară pas cu pas
Într-un slice sortat de 16 numere, căutarea lui 13 are nevoie de doar 4 verificări: intervalul se micșorează 16 → 8 → 4 → 2 și ajunge la indexul 6. O căutare liniară ar fi avut nevoie aici de 7 pași — și de până la 16.
Ieșire: program Go și rezultatul capturat
package main
import "fmt"
func main() {
nums := []int{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31}
target := 13
steps := 0
lo, hi := 0, len(nums)-1
for lo <= hi {
steps++
mid := (lo + hi) / 2
if nums[mid] == target {
fmt.Println("găsit", target, "la indexul", mid, "după", steps, "verificări")
break
}
if nums[mid] < target {
lo = mid + 1
} else {
hi = mid - 1
}
}
}
Căutare binară cu pachetul slices
slices.BinarySearch() găsește 9 la indexul 4. Valoarea lipsă 10 dă found == false și indexul 5 — locul în care 10 s-ar potrivi ca slice-ul să rămână sortat.
Ieșire: program Go și rezultatul capturat
package main
import (
"fmt"
"slices"
)
func main() {
nums := []int{1, 3, 5, 7, 9, 11, 13, 15}
i, found := slices.BinarySearch(nums, 9)
fmt.Println("index:", i, "găsit:", found)
i, found = slices.BinarySearch(nums, 10)
fmt.Println("index:", i, "găsit:", found)
}
O(n log n): sortarea
O(n log n) se află între liniar și pătratic și este complexitatea algoritmilor buni de sortare: datele sunt înjumătățite iar și iar (log n niveluri), iar fiecare nivel face o cantitate liniară de muncă (n).
În Go rareori scrii singur o sortare — slices.Sort() este O(n log n). Să sortezi o dată, apoi să faci căutare binară de multe ori, este un tipar frecvent și rapid.
Sortează un slice
slices.Sort() ordonează cele 8 numere în aproximativ 8 · log 8 = 24 pași — mult mai puțini decât cei 64 pe care i-ar folosi o sortare pătratică, iar diferența crește rapid pe măsură ce slice-ul se mărește.
Ieșire: program Go și rezultatul capturat
package main
import (
"fmt"
"slices"
)
func main() {
nums := []int{31, 5, 17, 1, 23, 9, 27, 13}
slices.Sort(nums)
fmt.Println(nums)
}