Timp constant O(1) în Python

Un pas, orice dimensiune

O(1) înseamnă timp constant: operația face același număr de pași, fie că datele de intrare au 5 elemente, fie un milion. Munca nu crește deloc.

Aceasta este cea mai bună complexitate posibilă. Operații O(1) tipice în Python sunt: citirea unui element din listă după index, citirea unei valori din dicționar după cheie, len(), adăugarea unui element și calculele matematice simple.

Observă ce nu înseamnă O(1): nu înseamnă „rapid”, ci înseamnă „nu devine mai lent când datele de intrare cresc”. Un pas constant poate fi totuși un pas lent — dar rămâne un singur pas.

Căutări în liste și dicționare

Un element al listei se află la o poziție cunoscută în memorie, așa că words[2] este un singur salt — calculatorul nu parcurge elementele dinaintea lui. Aceeași citire costă la fel într-o listă cu un milion de elemente.

O căutare în dicționar precum ages["Ben"] durează tot timp constant, în medie: cheia îi spune dicționarului direct unde este stocată valoarea. Cu paranteze pătrate, o cheie lipsă ridică un KeyError, de aceea căutările folosesc adesea ages.get("Ben") — aceasta returnează valoarea sau None când cheia lipsește.

Citește un element după index

Programul citește un element dintr-o listă cu 5 elemente și unul dintr-o listă cu un milion de elemente. Ambele citiri sunt un singur pas — lungimea listei nu contează.

Scrie un program Python cu o listă mică de 5 cuvinte și o listă mare de un milion de numere întregi, construită cu o list comprehension. Citește câte un element din fiecare după index și afișează-le pe amândouă, pentru a arăta că citirea după index este un singur pas, oricât de lungă ar fi lista.

> Ieșire: program Python complet

Prompt

Scrie un program Python cu o listă mică de 5 cuvinte și o listă mare de un milion de numere întregi, construită cu o list comprehension. Citește câte un element din fiecare după index și afișează-le pe amândouă, pentru a arăta că citirea după index este un singur pas, oricât de lungă ar fi lista.

Ieșire: program Python complet

words = ["one", "two", "three", "four", "five"]

big = [i * 2 for i in range(1000000)]

# Câte un singur pas, oricât de lungă ar fi lista.
print(words[2])
print(big[999999])

Citește o valoare după cheie

ages.get("Ben") găsește direct 25. Cheia lipsă "Dan" returnează None, iar get("Dan", 0) returnează în schimb valoarea de rezervă 0 — tot în timp constant.

Scrie un program Python cu un dicționar de la nume la vârste care conține Ana 30, Ben 25 și Cleo 41. Caută Ben cu get() și afișează rezultatul. Apoi caută cheia lipsă Dan cu get() și afișează rezultatul, și încă o dată cu get() și valoarea de rezervă 0.

> Ieșire: program Python complet

Prompt

Scrie un program Python cu un dicționar de la nume la vârste care conține Ana 30, Ben 25 și Cleo 41. Caută Ben cu get() și afișează rezultatul. Apoi caută cheia lipsă Dan cu get() și afișează rezultatul, și încă o dată cu get() și valoarea de rezervă 0.

Ieșire: program Python complet

ages = {"Ana": 30, "Ben": 25, "Cleo": 41}

print(ages.get("Ben"))

print(ages.get("Dan"))
print(ages.get("Dan", 0))

Adăugarea și calculele simple

append() adaugă un element la sfârșitul unei liste. De cele mai multe ori, acesta este un singur pas. (Din când în când lista trebuie să crească și este copiată, dar în medie costul pentru fiecare adăugare rămâne constant.)

Toate operațiile mici — atribuiri, adunări, comparații, interschimbarea a două valori — sunt și ele O(1). Ele sunt „pașii” în care se numără toate celelalte clase de complexitate.

Adaugă un element

append() pune "yellow" la sfârșit. Costul nu depinde de câte culori sunt deja în listă.

Scrie un program Python cu o listă care conține red, green, blue. Afișează lista și lungimea ei, adaugă yellow, apoi afișează din nou lista și lungimea ei.

> Ieșire: program Python complet

Prompt

Scrie un program Python cu o listă care conține red, green, blue. Afișează lista și lungimea ei, adaugă yellow, apoi afișează din nou lista și lungimea ei.

Ieșire: program Python complet

colors = ["red", "green", "blue"]
print("înainte:", colors, "lungime:", len(colors))

colors.append("yellow")
print("după:   ", colors, "lungime:", len(colors))

Interschimbă două valori

a, b = b, a interschimbă cele două valori într-un singur pas în timp constant — nu este nevoie de o variabilă ajutătoare.

Scrie un program Python cu două variabile a = 1 și b = 2. Afișează-le, interschimbă-le cu atribuirea dublă a, b = b, a, și afișează-le din nou.

> Ieșire: program Python complet

Prompt

Scrie un program Python cu două variabile a = 1 și b = 2. Afișează-le, interschimbă-le cu atribuirea dublă a, b = b, a, și afișează-le din nou.

Ieșire: program Python complet

a, b = 1, 2
print("înainte:", a, b)

a, b = b, a
print("după:   ", a, b)