De ce măsurăm algoritmii
Același program rulează repede pe un calculator nou și încet pe unul vechi. De aceea secundele sunt o modalitate proastă de a compara doi algoritmi — numărul depinde de mașină, nu doar de cod.
În schimb, numărăm pași: câte operații simple face algoritmul. Un pas este o acțiune mică, cum ar fi citirea unei valori, compararea a două numere sau adunarea lor.
Notația Big O descrie cum crește numărul de pași atunci când crește intrarea. Ea nu spune „asta durează 3 secunde”. Spune „dacă intrarea se dublează, munca se dublează” — adică O(n) — sau „dacă intrarea se dublează, munca rămâne aceeași” — adică O(1).
Big O se uită la cazul cel mai defavorabil: numărul maxim de pași de care algoritmul poate avea nevoie pentru o intrare de dimensiune n.
Numărarea pașilor
O buclă care vizitează fiecare element dintr-un slice face o trecere pentru fiecare element. Pentru 5 elemente înseamnă 5 pași, pentru 10 elemente 10 pași. Numărul de pași este același cu len(nums).
Nu ne interesează numărul exact. Ne interesează forma creșterii: de două ori intrarea, de două ori pașii. Această formă se numește liniară și se scrie O(n).
Numără pașii unei bucle
Funcția adaugă un contor steps++ în interiorul buclei. Un slice de 5 elemente cere 5 pași, un slice de 10 elemente cere 10 pași — numărul urmează dimensiunea intrării.
Ieșire: program Go și rezultatul capturat
package main
import "fmt"
func countSteps(nums []int) int {
steps := 0
sum := 0
for _, n := range nums {
sum += n
steps++
}
fmt.Println("suma:", sum)
return steps
}
func main() {
small := []int{2, 4, 6, 8, 10}
big := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
fmt.Println("pași pentru 5 elemente:", countSteps(small))
fmt.Println("pași pentru 10 elemente:", countSteps(big))
}
Dublarea intrării dublează munca
Programul rulează aceeași buclă de numărare pentru n = 100, 200 și 400. De fiecare dată când n se dublează, se dublează și numărul de pași. Aceasta este amprenta lui O(n).
Ieșire: program Go și rezultatul capturat
package main
import "fmt"
func main() {
for _, n := range []int{100, 200, 400} {
steps := 0
for i := 0; i < n; i++ {
steps++
}
fmt.Printf("n = %3d -> %3d pași\n", n, steps)
}
}
Clasele de creștere
Majoritatea algoritmilor se încadrează în câteva clase de creștere comune, de la cea mai rapidă la cea mai lentă:
O(1) constant — munca nu crește niciodată.O(log n) logaritmic — dublarea intrării adaugă un singur pas.O(n) liniar — munca crește odată cu intrarea.O(n log n) — un algoritm bun de sortare.O(n²) pătratic — o buclă în interiorul altei bucle.O(2ⁿ) exponențial — munca se dublează cu fiecare element în plus.
Pentru intrări mici diferența este minusculă. Pentru intrări mari ea decide dacă programul răspunde imediat sau nu se termină niciodată.
Compară clasele de creștere
Tabelul arată numărul de pași pentru valori din ce în ce mai mari ale lui n. La n = 16, log n este doar 4, în timp ce 2ⁿ este deja 65536. Cu cât n devine mai mare, cu atât clasele se îndepărtează mai mult una de alta.
Ieșire: program Go și rezultatul capturat
package main
import (
"fmt"
"math"
)
func main() {
fmt.Printf("%5s %7s %5s %9s %6s %8s\n", "n", "log n", "n", "n log n", "n^2", "2^n")
for _, n := range []int{1, 2, 4, 8, 16} {
logn := math.Log2(float64(n))
fmt.Printf("%5d %7.0f %5d %9.0f %6d %8d\n",
n, logn, n, float64(n)*logn, n*n, int(math.Pow(2, float64(n))))
}
}
Ce ignoră Big O
Big O păstrează doar forma creșterii și aruncă detaliile. O(2n), O(n + 5) și O(n) sunt toate aceeași clasă: liniară.
De ce? Pentru că la intrări mari factorul constant nu mai contează. Un algoritm care face 2 treceri peste un milion de elemente este totuși într-o cu totul altă lume decât unul care compară fiecare element cu fiecare alt element.
Regulile exacte de simplificare — renunțăm la constante, renunțăm la termenii mai mici — au propria lor pagină mai târziu în acest grup.
Două bucle înseamnă tot O(n)
Programul face două treceri separate peste slice: una pentru sumă, una pentru cea mai mare valoare. Asta înseamnă 2n pași — 16 pentru 8 elemente. Big O renunță la constanta 2, deci acest lucru este tot O(n).
Ieșire: program Go și rezultatul capturat
package main
import "fmt"
func main() {
nums := []int{3, 1, 4, 1, 5, 9, 2, 6}
steps := 0
sum := 0
for _, n := range nums {
sum += n
steps++
}
max := nums[0]
for _, n := range nums {
if n > max {
max = n
}
steps++
}
fmt.Println("suma:", sum)
fmt.Println("maxim:", max)
fmt.Println("elemente:", len(nums))
fmt.Println("pași:", steps)
}