Căutarea unui element într-un dicționar (dict) în Python are de obicei o complexitate temporară amortizată de O(1), adică constantă. Acest lucru se realizează prin utilizarea unui tabel de dispersie.

Cu toate acestea, în cazuri rare, de exemplu, atunci când există multe coliziuni sau dacă funcția hash distribuie prost cheile, complexitatea poate să se înrăutățească până la O(n), unde n este numărul de elemente din dicționar.

Prin urmare, căutarea nu este întotdeauna strict O(1), dar în practică și în cele mai multe cazuri, este exact așa.

Anterior În continuare