Временная сложность алгоритма

Временная сложность алгоритма — это оценка того, как изменяется время выполнения алгоритма в зависимости от размера входных данных.

---

📌 Основные моменты, которые стоит сказать

1. Зачем нужна Чтобы понять, насколько алгоритм будет масштабируемым и как он поведёт себя на больших данных.

2. Обозначения (Big O)

   • O(1) — константное время (не зависит от размера входа). Пример: доступ к элементу списка по индексу.

   • O(log n) — логарифмическое время. Пример: бинарный поиск.

   • O(n) — линейное время. Пример: один цикл по массиву.

   • O(n log n) — логлинейное время. Пример: быстрая сортировка.

   • O(n²) — квадратичное время. Пример: вложенные циклы.

   • O(2ⁿ) — экспоненциальное время. Пример: перебор всех комбинаций.

   • O(n!) — факториальное время. Пример: полный перебор перестановок.

3. Как измерять

   • Считаем количество операций, а не реальное время.

   • Берём асимптотическую оценку (смотрим поведение при n → ∞).

---

📊 Пример в Python

# O(1)
def get_first_element(lst):
    return lst[0]

# O(n)
def sum_list(lst):
    total = 0
    for num in lst:
        total += num
    return total

# O(n^2)
def pairs(lst):
    for i in lst:
        for j in lst:
            print(i, j)

---

📌 Временная сложность в Python

Операция	Список (list)	Множество (set)	Словарь (dict)
Доступ по индексу	O(1)	—	—
Присвоение по индексу	O(1)	—	—
Поиск элемента	O(n)	O(1) avg, O(n) worst	O(1) avg, O(n) worst
Добавление в конец	O(1) амортиз.	O(1)	O(1)
Вставка в начало	O(n)	—	—
Вставка в середину	O(n)	—	—
Удаление по значению	O(n)	O(1) avg	O(1) avg
Итерирование	O(n)	O(n)	O(n)
Получение всех ключей (.keys())	—	—	O(1)
Получение всех значений (.values())	—	—	O(1)
Копирование (copy())	O(n)	O(n)	O(n)

---

💡 Пояснения:

• avg — средний случай (обычно при хорошей хэш-функции).

• worst — худший случай (например, при коллизиях в хэш-таблице).

• Амортизированная сложность (например, добавление в конец списка) учитывает, что иногда Python выделяет больше памяти, чем нужно, чтобы ускорить добавления.

---

📊 Пример проверки производительности

import time

def measure_time(func, *args):
    start = time.time()
    func(*args)
    return time.time() - start

# Пример: поиск элемента в списке vs множестве
lst = list(range(10_000_000))
s = set(lst)

print("List search:", measure_time(lambda: 9999999 in lst))
print("Set search:", measure_time(lambda: 9999999 in s))

На практике set и dict работают в десятки раз быстрее при поиске.