O buclă în interiorul unei bucle
O(n²) înseamnă timp pătratic: volumul de lucru crește cu pătratul intrării. 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.
Forma care o dă de gol în cod este o buclă în interiorul unei bucle, ambele parcurgând aceleași date. Bucla exterioară rulează n ori, iar pentru fiecare dintre acestea bucla interioară rulează din nou n ori: n · n pași.
Complexitatea pătratică este acceptabilă pentru tablouri 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.
Construirea fiecărei perechi
Bucla exterioară alege $x, bucla interioară îl împerechează cu fiecare $y. 4 elemente produc 16 perechi — pătratul dimensiunii intrării.
Ieșire: script PHP
<?php
$letters = ["a", "b", "c", "d"];
$pairs = 0;
foreach ($letters as $x) {
foreach ($letters as $y) {
echo $x . $y, " ";
$pairs++;
}
echo "\n";
}
echo count($letters), " elemente au format ", $pairs, " perechi\n";
Bubble sort
Bubble sort este algoritmul pătratic clasic: parcurge tabloul în mod repetat și interschimbă vecinii aflați în ordine greșită. Valorile mari „urcă la suprafață” 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: funcția sort() integrată în PHP 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 circa zece mii.
Ieșire: script PHP
<?php
$nums = [5, 3, 8, 1, 4];
$comparisons = 0;
$n = count($nums);
for ($i = 0; $i < $n - 1; $i++) {
for ($j = 0; $j < $n - 1 - $i; $j++) {
$comparisons++;
if ($nums[$j] > $nums[$j + 1]) {
[$nums[$j], $nums[$j + 1]] = [$nums[$j + 1], $nums[$j]];
}
}
}
echo "sortat: ", implode(", ", $nums), "\n";
echo "comparații: ", $comparisons, "\n";
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țială din acest grup arată trucul standard care face acest lucru liniar: reține valorile pe care le-ai văzut deja într-un tablou asociativ.
Găsirea unui duplicat cu două bucle
Fiecare element este comparat cu fiecare element ulterior. Perechea duplicată de valori 1 este găsită după 7 verificări; în cazul cel mai defavorabil — niciun duplicat — rulează toate cele 15 verificări de perechi.
Ieșire: script PHP
<?php
$nums = [3, 1, 4, 1, 5, 9];
$checks = 0;
$n = count($nums);
for ($i = 0; $i < $n; $i++) {
for ($j = $i + 1; $j < $n; $j++) {
$checks++;
if ($nums[$i] === $nums[$j]) {
echo "duplicat: ", $nums[$i], " după ", $checks, " verificări\n";
}
}
}