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

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

***

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

1. **Зачем нужна**\
   Чтобы понять, насколько алгоритм будет масштабируемым и как он поведёт себя на больших данных.
2. **Обозначения (Big O)**
   * **O(1)** — константное время (не зависит от размера входа).\
     \&#xNAN;*Пример:* доступ к элементу списка по индексу.
   * **O(log n)** — логарифмическое время.\
     \&#xNAN;*Пример:* бинарный поиск.
   * **O(n)** — линейное время.\
     \&#xNAN;*Пример:* один цикл по массиву.
   * **O(n log n)** — логлинейное время.\
     \&#xNAN;*Пример:* быстрая сортировка.
   * **O(n²)** — квадратичное время.\
     \&#xNAN;*Пример:* вложенные циклы.
   * **O(2ⁿ)** — экспоненциальное время.\
     \&#xNAN;*Пример:* перебор всех комбинаций.
   * **O(n!)** — факториальное время.\
     \&#xNAN;*Пример:* полный перебор перестановок.
3. **Как измерять**
   * Считаем количество операций, а не реальное время.
   * Берём **асимптотическую оценку** (смотрим поведение при n → ∞).

***

### 📊 Пример в Python

```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 выделяет больше памяти, чем нужно, чтобы ускорить добавления.

***

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

```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` работают в десятки раз быстрее при поиске.
