O buclă în interiorul altei bucle
O(n²) înseamnă timp pătratic: munca crește cu pătratul datelor de intrare. De două ori mai multe elemente, de patru ori mai mulți pași. De zece ori mai multe elemente, de o sută de ori mai mulți pași.
Semnul distinctiv în cod este o buclă în interiorul altei bucle, ambele parcurgând aceleași date. Bucla exterioară rulează de n ori, iar pentru fiecare dintre acestea bucla interioară rulează din nou de n ori: n · n pași.
Timpul pătratic este acceptabil pentru slice-uri mici. Pentru 100.000 de elemente înseamnă deja 10 miliarde de pași — acolo încep programele să se blocheze.
Toate perechile
Cea mai directă sarcină O(n²): combină fiecare element cu fiecare element. 4 litere formează 4 · 4 = 16 perechi; 100 de litere ar forma 10.000.
Construiește fiecare pereche
Bucla exterioară alege x, iar bucla interioară îl împerechează cu fiecare y. 4 elemente produc 16 perechi — pătratul dimensiunii intrării.
Ieșire: program Go și rezultatul capturat
package main
import "fmt"
func main() {
letters := []string{"a", "b", "c", "d"}
pairs := 0
for _, x := range letters {
for _, y := range letters {
fmt.Print(x+y, " ")
pairs++
}
fmt.Println()
}
fmt.Println(len(letters), "elemente au format", pairs, "perechi")
}
Sortare prin bule
Sortarea prin bule este algoritmul pătratic clasic: parcurge slice-ul în mod repetat și interschimbă vecinii aflați în ordine greșită. Valorile mari „urcă” spre final, câte o trecere pe rând.
Cu cele două bucle imbricate face aproximativ n²/2 comparații. Este un algoritm excelent din care să înveți — și unul prost de folosit: slices.Sort() face aceeași treabă în O(n log n).
Sortare cu două bucle imbricate
Sortarea a 5 elemente cere 4 + 3 + 2 + 1 = 10 comparații. Pentru 1.000 de elemente ar fi aproximativ o jumătate de milion — în timp ce o sortare O(n log n) are nevoie de aproximativ zece mii.
Ieșire: program Go și rezultatul capturat
package main
import "fmt"
func main() {
nums := []int{5, 3, 8, 1, 4}
comparisons := 0
for i := 0; i < len(nums)-1; i++ {
for j := 0; j < len(nums)-1-i; j++ {
comparisons++
if nums[j] > nums[j+1] {
nums[j], nums[j+1] = nums[j+1], nums[j]
}
}
}
fmt.Println("sortat:", nums)
fmt.Println("comparații:", comparisons)
}
Duplicate pe calea lentă
Verificarea fiecărui element față de fiecare element care vine după el este un alt tipar cu bucle imbricate — compararea tuturor perechilor pentru a găsi un duplicat.
Funcționează, dar este O(n²). Pagina despre complexitatea spațiului din acest grup arată trucul standard care face acest lucru liniar: reține într-un map valorile pe care le-ai văzut deja.
Găsește un duplicat cu două bucle
Fiecare element este comparat cu fiecare element de după el. Perechea duplicată de 1 este găsită după 7 verificări; în cel mai rău caz — niciun duplicat — se execută toate cele 15 verificări de perechi.
Ieșire: program Go și rezultatul capturat
package main
import "fmt"
func main() {
nums := []int{3, 1, 4, 1, 5, 9}
checks := 0
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
checks++
if nums[i] == nums[j] {
fmt.Println("duplicat:", nums[i], "după", checks, "verificări")
}
}
}
}