De ce contează?
Vrei să ajungi în vârful unui bloc cu 100 de etaje. Ai două opțiuni: iei liftul, care te duce direct, dintr-o apăsare de buton — sau urci scările, treaptă cu treaptă. Dacă există lift (o formulă), de ce ai urca 100 de trepte? Dar uneori liftul pur și simplu nu există, și atunci singura cale sigură e tot pas cu pas. A ști când ai lift și când nu — asta decide dacă programul tău face un calcul sau un milion.
Ideea-cheie
Pentru multe șiruri, ca să afli al n-lea termen sau suma primilor n termeni,
ai două drumuri. Primul: o formulă închisă care îți dă răspunsul printr-un
singur calcul, indiferent cât de mare e n — liftul. Al doilea: simularea,
adică generezi termenii unul câte unul și aduni pe parcurs — scările.
Ambele dau același rezultat corect. Diferența e cât te costă. Formula sare direct
la răspuns, deci e O(1). Simularea trece prin toate cele n valori, deci e
O(n). Întrebarea care decide totul nu e „pot să rezolv?”, ci „există o
formulă pentru acest șir, și o cunosc?”.
Gândește-te la fiecare șir cu o întrebare simplă: pot calcula termenul direct
din n, sau am nevoie de termenii dinaintea lui? Dacă pot direct, am formulă și
sar la răspuns în O(1). Dacă fiecare termen depinde de cei dinaintea lui și
nu pot scurta drumul, trebuie să-i parcurg pe toți: simulare în O(n).