Какова сложность основных операций с коллекциями в Python?

Сложность основных операций с коллекциями в Python (список, словарь, множество) можно представить в виде таблицы:

Пояснения:

• 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) в среднем (amortized)
my_list = [1, 2, 3]
my_list.append(4) # O(1) в среднем

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

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