Ποια είναι η χρονική πολυπλοκότητα της προσθήκης και διαγραφής ενός στοιχείου σε ένα λεξικό στην Python;

Στην Python, το λεξικό υλοποιείται με βάση έναν πίνακα κατακερματισμού, που εξασφαλίζει κατά μέσο όρο μια πολυπλοκότητα χρόνου O(1) για τις λειτουργίες προσθήκης και διαγραφής στοιχείων.

• Προσθήκη στοιχείου: υπολογίζεται το κατακερματιστικό της κλειδιού και το στοιχείο εισάγεται στο αντίστοιχο κελί. Μέσος όρος, αυτό απαιτεί σταθερό χρόνο.
• Διαγραφή στοιχείου: επίσης γίνεται μέσω του κατακερματισμού της κλειδιού και, κατά μέσο όρο, διαρκεί O(1).

Ωστόσο, στην χειρότερη περίπτωση (π.χ., με πολλές συγκρούσεις), οι λειτουργίες μπορεί να υποβαθμιστούν σε O(n), όπου n είναι ο αριθμός των στοιχείων στο λεξικό, αλλά τέτοιες περιπτώσεις είναι εξαιρετικά σπάνιες χάρη σε καλή υλοποίηση και δυναμική επέκταση του λεξικού.

Παράδειγμα:

my_dict = {}
my_dict['key'] = 'value'  # προσθήκη — O(1)
del my_dict['key']          # διαγραφή — O(1)