Împarte problema în două
O(log n) înseamnă timp logaritmic: fiecare pas reduce la jumătate munca rămasă. Pentru că înjumătățirea micșorează numerele atât de repede, dublarea intrării adaugă doar un pas în plus.
16 elemente cer 4 înjumătățiri, 32 de elemente cer 5, un milion aproximativ 20, un miliard aproximativ 30. De aceea algoritmii logaritmici par instantanei chiar și pe date uriașe.
Exemplul clasic este căutarea binară — dar ea funcționează numai pe date sortate. Înjumătățirea are nevoie de o ordine ca să știe care jumătate poate fi aruncată.
O buclă de înjumătățire
Cel mai simplu mod de a vedea O(log n) este o buclă care împarte n la 2 până ajunge la 1. Numărul de runde este logaritmul lui n: pentru n = 16 bucla rulează de 4 ori, pentru că 2 · 2 · 2 · 2 = 16.
Înjumătățire până rămâne unu
16 devine 8, 4, 2, 1 — patru pași. Dublarea lui n la 32 ar adăuga doar un singur pas în plus.
Ieșire: program TypeScript și rezultatul capturat
let n = 16
let steps = 0
while (n > 1) {
n = Math.floor(n / 2)
steps++
console.log("n este acum", n)
}
console.log("16 a devenit 1 în", steps, "pași")
Căutarea binară
Căutarea binară găsește o valoare într-un tablou sortat verificând mereu elementul din mijloc. Dacă mijlocul este prea mic, toată jumătatea din stânga este aruncată; dacă este prea mare, jumătatea din dreapta. Fiecare verificare înjumătățește intervalul de căutare.
Două marcaje, lo și hi, țin intervalul curent. Bucla se termină când valoarea este găsită sau când intervalul este gol.
TypeScript nu are o căutare binară proprie. Căutările încorporate — indexOf() și includes() — parcurg tabloul de la început, deci rămân O(n) chiar și atunci când datele sunt deja sortate. Pe date sortate, bucla scrisă de mână este cea mai rapidă.
Căutarea binară pas cu pas
Într-un tablou sortat de 16 numere, căutarea lui 13 are nevoie de doar 4 verificări: intervalul se micșorează 16 → 8 → 4 → 2 și se oprește la indexul 6. O căutare liniară ar fi avut nevoie aici de 7 pași — și de până la 16.
Ieșire: program TypeScript și rezultatul capturat
const nums = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31]
const target = 13
let steps = 0
let lo = 0
let hi = nums.length - 1
while (lo <= hi) {
steps++
const mid = Math.floor((lo + hi) / 2)
if (nums[mid] === target) {
console.log("găsit", target, "la indexul", mid, "după", steps, "verificări")
break
}
if (nums[mid] < target) {
lo = mid + 1
} else {
hi = mid - 1
}
}
Căutarea încorporată este tot liniară
Ambele căutări sunt de acord: 9 se află la indexul 4. Dar indexOf() ajunge acolo testând 5 elemente, în timp ce căutarea binară are nevoie de 3 verificări. Pentru valoarea lipsă 10, indexOf() testează toate cele 8 elemente și returnează -1; căutarea binară se oprește după 3 verificări și poate chiar să raporteze indexul 5 — locul unde ar încăpea 10 ca tabloul să rămână sortat.
Cu 8 elemente diferența este mică. Cu un milion sunt aproximativ 1.000.000 de pași față de 20.
Ieșire: program TypeScript și rezultatul capturat
const nums = [1, 3, 5, 7, 9, 11, 13, 15]
// Câte elemente trebuie să atingă parcurgerea încorporată: ea pornește de la început.
function scanned(xs: number[], target: number): number {
let steps = 0
xs.findIndex((x) => {
steps++
return x === target
})
return steps
}
interface Found {
index: number
checks: number
insertAt: number
}
// Căutarea binară scrisă de mână: fiecare verificare înjumătățește intervalul.
function binarySearch(xs: number[], target: number): Found {
let lo = 0
let hi = xs.length - 1
let checks = 0
while (lo <= hi) {
checks++
const mid = Math.floor((lo + hi) / 2)
if (xs[mid] === target) {
return { index: mid, checks, insertAt: mid }
}
if (xs[mid] < target) {
lo = mid + 1
} else {
hi = mid - 1
}
}
return { index: -1, checks, insertAt: lo }
}
for (const target of [9, 10]) {
console.log("țintă", target)
console.log(" indexOf:", nums.indexOf(target), "includes:", nums.includes(target),
"- parcurse", scanned(nums, target), "din", nums.length, "elemente")
const hit = binarySearch(nums, target)
if (hit.index >= 0) {
console.log(" căutare binară: indexul", hit.index, "după", hit.checks, "verificări")
} else {
console.log(" căutare binară: negăsit după", hit.checks, "verificări -",
target, "ar încăpea la indexul", hit.insertAt)
}
}
O(n log n): sortarea
O(n log n) se află între liniar și pătratic și este complexitatea algoritmilor buni de sortare: datele sunt înjumătățite din nou și din nou (log n niveluri), iar fiecare nivel face o cantitate liniară de muncă (n).
Rareori scrii singur o sortare — fiecare tablou are deja sort(), iar acesta este O(n log n). Sortarea o dată, apoi căutarea binară de multe ori, este un tipar obișnuit și rapid.
Sortarea unui tablou
nums.sort((a, b) => a - b) ordonează cele 8 numere în aproximativ 8 · log 8 = 24 pași — mult mai puțini decât cei 64 pe care i-ar folosi o sortare pătratică, iar diferența crește repede pe măsură ce tabloul se mărește.
Comparatorul nu este opțional aici. Apelat fără el, sort() compară valorile ca text: "13" începe cu 1, deci ajunge înaintea lui "5". Programul afișează ambele ordini.
Ieșire: program TypeScript și rezultatul capturat
const nums = [31, 5, 17, 1, 23, 9, 27, 13]
const show = (xs: number[]): string => `[ ${xs.join(", ")} ]`
// Fără comparator, sort() compară valorile ca text.
console.log("ca text: ", show([...nums].sort()))
// Cu un comparator numeric, ordinea este cea dorită.
console.log("ca numere:", show([...nums].sort((a, b) => a - b)))