Каква е сложността на основните операции с колекции в Python?

Сложността на основните операции с колекции в Python (списък, речник, множество) може да бъде представена под формата на таблица:

Операция	Списък (list)	Речник (dict)	Множество (set)
Търсене на елемент	O(n)	O(1)	O(1)
Вмъкване на елемент	O(n)	O(1)	O(1)
Изтриване на елемент	O(n)	O(1)	O(1)
Достъп по индекс	O(1)	N/A	N/A
Итерация	O(n)	O(n)	O(n)
Дължина на колекция	O(1)	O(1)	O(1)

Обяснения:

• O(1) - Константна сложност: Операцията се изпълнява за фиксирано време, независимо от размера на колекцията.
• O(n) - Линейна сложност: Времето за изпълнение на операцията е пропорционално на размера на колекцията.
• Търсене, вмъкване и изтриване в списъци изискват преместване на елементите, което отнема време в зависимост от позицията на елемента и размера на списъка.
• Речници и множества използват хеш таблици, което осигурява средно константно време за търсене, вмъкване и изтриване. При колизии на хешове тези операции могат да се влошат до O(n), но в практиката това се случва рядко.
• Достъп по индекс в списъците е O(1), тъй като елементите се съхраняват последователно в паметта.
• Итерация през всички елементи на колекцията винаги отнема време, пропорционално на тяхното количество (O(n)).
• Получаване на дължината на колекцията (len()) е O(1) за всички тези типове колекции, тъй като дължината се съхранява отделно.

Пример за търсене на елемент в списък:

# Търсене на елемент в списък изисква обхождане
my_list = [1, 2, 3, 4, 5]
if 3 in my_list:
    pass # O(n) в най-лошия случай

Пример за търсене на елемент в речник:

# Търсене на елемент в речник - O(1) средно
my_dict = {'a': 1, 'b': 2, 'c': 3}
if 'b' in my_dict:
    pass # O(1) средно

Пример за добавяне на елемент в края на списъка:

# Добавяне на елемент в края на списъка - O(1) средно (амортизирано)
my_list = [1, 2, 3]
my_list.append(4) # O(1) средно

Пример за добавяне на елемент в началото на списъка:

# Добавяне на елемент в началото на списъка - O(n)
my_list = [1, 2, 3]
my_list.insert(0, 0) # O(n)