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 TypeScript, timpul liniar arată de obicei ca o singură buclă for peste un tablou sau peste un Map. Orice algoritm care trebuie măcar să se uite la fiecare element — însumare, 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ă trecere.
Căutare liniară
Când tabloul nu este sortat, singura cale 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. Acel 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 TypeScript și rezultatul capturat
const words = ["one", "two", "three", "four", "five"]
let steps = 0
for (let i = 0; i < words.length; i++) {
steps++
if (words[i] === "four") {
console.log("găsit la indexul", i, "după", steps, "pași")
break
}
}
Vizitarea fiecărui element
Multe sarcini obișnuite sunt o singură trecere prin tot tabloul: 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 la rând tot liniar înseamnă — O(2n) și O(3n) se reduc la O(n).
Însumează toate elementele
Bucla adună fiecare element la sum. 8 elemente, 8 adunări — forma clasică a unei singure treceri.
Ieșire: program TypeScript și rezultatul capturat
const nums = [3, 1, 4, 1, 5, 9, 2, 6]
let sum = 0
for (const n of nums) {
sum += n
}
console.log("suma a", nums.length, "elemente:", sum)
Găsește cea mai mare valoare
biggest pornește de la 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 TypeScript și rezultatul capturat
const nums = [3, 1, 4, 1, 5, 9, 2, 6]
let biggest = nums[0]
for (let i = 1; i < nums.length; i++) {
if (nums[i] > biggest) {
biggest = nums[i]
}
}
console.log("cea mai mare valoare:", biggest)
Numără potrivirile
Bucla testează fiecare cuvânt cu w.length > 3 și numără potrivirile. Trei cuvinte sunt mai lungi de 3 litere.
Ieșire: program TypeScript și rezultatul capturat
const words = ["one", "two", "three", "four", "five"]
let count = 0
for (const w of words) {
if (w.length > 3) {
count++
}
}
console.log(count, "cuvinte sunt mai lungi de 3 litere")