O singură parcurgere a datelor
O(n) înseamnă timp liniar: munca crește în pas cu intrarea. De două ori mai multe elemente, de două ori mai mulți pași.
În PHP, timpul liniar arată de obicei ca o singură buclă foreach peste un tablou. Orice algoritm care trebuie măcar să se uite la fiecare element — adunare, numărare, căutare într-un tablou nesortat — nu poate fi mai rapid decât O(n).
Liniar este o complexitate bună. Milioane de elemente nu sunt o problemă pentru o singură parcurgere.
Căutare liniară
Când tabloul nu este sortat, singura modalitate 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 trece prin toate cele n elemente. Acest caz cel mai defavorabil este cel pe care îl descrie O(n).
Găsește o valoare și poziția ei
Bucla verifică "one", "two", "three" înainte de a ajunge la "four" — 4 pași pentru o potrivire la indexul 3. break oprește bucla imediat ce valoarea este găsită.
Ieșire: script PHP
<?php
$words = ["one", "two", "three", "four", "five"];
$steps = 0;
foreach ($words as $i => $w) {
$steps++;
if ($w === "four") {
echo "găsit la indexul $i după $steps pași\n";
break;
}
}
Trecerea prin fiecare element
Multe sarcini de zi cu zi sunt o singură parcurgere a întregului tablou: adună toate valorile, păstrează cea mai mare văzută până acum, numără elementele care trec un test. Fiecare element este atins exact o dată, deci toate sunt O(n).
Două sau trei astfel de parcurgeri una după alta rămân 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 parcurgeri.
Ieșire: script PHP
<?php
$nums = [3, 1, 4, 1, 5, 9, 2, 6];
$sum = 0;
foreach ($nums as $n) {
$sum += $n;
}
echo "suma a ", count($nums), " elemente: $sum\n";
Găsește cea mai mare valoare
$max pornește cu primul element; fiecare element mai mare îl înlocuiește. După o singură parcurgere rămâne cea mai mare valoare, 9.
Ieșire: script PHP
<?php
$nums = [3, 1, 4, 1, 5, 9, 2, 6];
$max = $nums[0];
foreach ($nums as $n) {
if ($n > $max) {
$max = $n;
}
}
echo "cea mai mare valoare: $max\n";
Numără potrivirile
Bucla testează fiecare cuvânt cu strlen($w) > 3 și numără potrivirile. Trei cuvinte au mai mult de 3 litere.
Ieșire: script PHP
<?php
$words = ["one", "two", "three", "four", "five"];
$count = 0;
foreach ($words as $w) {
if (strlen($w) > 3) {
$count++;
}
}
echo "$count cuvinte au mai mult de 3 litere\n";