O singură trecere prin date
O(n) înseamnă timp liniar: munca crește în pas cu datele de intrare. De două ori mai multe elemente, de două ori mai mulți pași.
În Go, timpul liniar arată de obicei ca o singură buclă for peste un slice sau o map. Orice algoritm care trebuie măcar să se uite la fiecare element — adunare, numărare, căutare într-un slice nesortat — nu poate fi mai rapid de O(n).
Liniar este o complexitate bună. Milioane de elemente nu sunt o problemă pentru o singură trecere.
Căutare liniară
Când slice-ul nu este sortat, singurul mod de a găsi o valoare este să verifici elementele unul câte unul, de la început. Aceasta este o căutare liniară.
În cazul cel mai defavorabil — valoarea este ultima sau nu există deloc — bucla vizitează toate cele n elemente. Acest caz defavorabil este ceea ce descrie O(n).
Găsește o valoare și poziția ei
Bucla verifică "one", "two", "three" înainte să ajungă la "four" — 4 pași pentru o potrivire la indexul 3. break oprește bucla imediat ce valoarea este găsită.
Ieșire: program Go și rezultatul capturat
package main
import "fmt"
func main() {
words := []string{"one", "two", "three", "four", "five"}
steps := 0
for i, w := range words {
steps++
if w == "four" {
fmt.Println("găsit la indexul", i, "după", steps, "pași")
break
}
}
}
Vizitarea fiecărui element
Multe sarcini de zi cu zi sunt o singură trecere peste tot slice-ul: adună toate valorile, păstrează cea mai mare valoare văzută până acum, numără elementele care trec un test. Fiecare element este atins exact o dată, așa că toate sunt O(n).
Două sau trei astfel de treceri una după alta rămân tot liniare — O(2n) și O(3n) se reduc la O(n).
Adună toate elementele
Bucla adaugă fiecare element la sum. 8 elemente, 8 adunări — forma clasică a unei singure treceri.
Ieșire: program Go și rezultatul capturat
package main
import "fmt"
func main() {
nums := []int{3, 1, 4, 1, 5, 9, 2, 6}
sum := 0
for _, n := range nums {
sum += n
}
fmt.Println("suma a", len(nums), "elemente:", sum)
}
Găsește cea mai mare valoare
max pornește ca primul element; orice alt element mai mare îl înlocuiește. După o singură trecere rămâne cea mai mare valoare, 9.
Ieșire: program Go și rezultatul capturat
package main
import "fmt"
func main() {
nums := []int{3, 1, 4, 1, 5, 9, 2, 6}
max := nums[0]
for _, n := range nums[1:] {
if n > max {
max = n
}
}
fmt.Println("cea mai mare valoare:", max)
}
Numără potrivirile
Bucla testează fiecare cuvânt cu len(w) > 3 și numără potrivirile. Trei cuvinte au mai mult de 3 litere.
Ieșire: program Go și rezultatul capturat
package main
import "fmt"
func main() {
words := []string{"one", "two", "three", "four", "five"}
count := 0
for _, w := range words {
if len(w) > 3 {
count++
}
}
fmt.Println(count, "cuvinte au mai mult de 3 litere")
}