O singură trecere prin date
O(n) înseamnă timp liniar: munca crește în același ritm cu intrarea. De două ori mai multe elemente, de două ori mai mulți pași.
În Python, timpul liniar arată de obicei ca o singură buclă for peste o listă sau un dicționar. Orice algoritm care trebuie cel puțin să privească fiecare element — adunarea, numărarea, căutarea într-o listă 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 lista 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 cel mai rău caz — valoarea este ultima sau nu există deloc — bucla vizitează toate cele n elemente. Acest cel mai rău caz 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 Python complet
words = ["one", "two", "three", "four", "five"]
steps = 0
for i, w in enumerate(words):
steps += 1
if w == "four":
print("găsit la indexul", i, "după", steps, "pași")
break
Vizitarea fiecărui element
Multe sarcini obișnuite sunt o singură trecere prin toată lista: 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ă, deci toate sunt O(n).
Două sau trei astfel de treceri una după alta sunt tot liniare — O(2n) și O(3n) se reduc la O(n).
Adună toate elementele
Bucla adaugă fiecare element la total. 8 elemente, 8 adunări — forma clasică a unei singure treceri.
Ieșire: program Python complet
nums = [3, 1, 4, 1, 5, 9, 2, 6]
total = 0
for n in nums:
total += n
print("suma celor", len(nums), "elemente:", total)
Găsește cea mai mare valoare
biggest pornește ca primul element; fiecare alt element mai mare îl înlocuiește. După o singură trecere rămâne cea mai mare valoare, 9.
Ieșire: program Python complet
nums = [3, 1, 4, 1, 5, 9, 2, 6]
biggest = nums[0]
for n in nums[1:]:
if n > biggest:
biggest = n
print("cea mai mare valoare:", biggest)
Numără potrivirile
Bucla testează fiecare cuvânt cu len(w) > 3 și numără potrivirile. Trei cuvinte sunt mai lungi de 3 litere.
Ieșire: program Python complet
words = ["one", "two", "three", "four", "five"]
count = 0
for w in words:
if len(w) > 3:
count += 1
print(count, "cuvinte sunt mai lungi de 3 litere")