Big O: Язык эффективности

Цели урока

• Понять зачем измерять эффективность алгоритмов
• Освоить нотацию Big O и правила упрощения
• Различать O(1), O(log n), O(n), O(n log n), O(n²)
• Научиться определять сложность по коду

Предварительные знания

• Циклы в программировании

• Циклы

В 2006 году Google отклонил разработчика, чей код работал. Причина? O(n²) вместо O(n log n). При масштабах Google это разница между миллисекундами и часами. Big O - язык, на котором говорят все серьёзные разработчики.

• Google/Facebook - миллиарды запросов, O(n²) = смерть серверов
• Игры - 60 FPS = 16мс на кадр, каждая миллисекунда важна
• Финтех - HFT трейдинг, наносекунды решают
• Собеседования - первый вопрос после решения: 'Какая сложность?'

История Big O

Немецкий математик Пауль Бахман ввёл O-нотацию в 1894 году в книге 'Die Analytische Zahlentheorie'. Позже Эдмунд Ландау популяризировал её, поэтому иногда называют 'символ Ландау'. В computer science Big O стал стандартом благодаря Дональду Кнуту.

Зачем измерять скорость?

**Два программиста решают одну задачу.** Оба кода работают. Но один обрабатывает миллион записей за секунду, другой - за час.

**Разница в миллионы раз!** Выбор алгоритма важнее, чем мощность компьютера.

Big O - язык сложности

**Big O** описывает, как растёт время работы алгоритма при увеличении входных данных.

Big O отвечает на вопрос: **"Если данных станет в 10 раз больше, во сколько раз дольше будет работать?"**

**Ключевые правила Big O:**

1. **Игнорируем константы:** O(2n) = O(n), O(500) = O(1)
2. **Берём доминирующий член:** O(n² + n) = O(n²)
3. **Худший случай:** если алгоритм иногда быстр, иногда медленный - берём медленный

O(1) и O(n): Константа и линейный рост

O(1) - Константное время

Время **не зависит** от размера входных данных.

O(n) - Линейное время

Время растёт **пропорционально** размеру данных.

**Подсказка:** один цикл по всем элементам = O(n)

O(n^2): Вложенные циклы

**O(n²)** - время растёт как квадрат размера данных. Обычно = вложенные циклы.

**O(n²) опасен!** При n = 10,000 → 100,000,000 операций. При n = 100,000 → 10,000,000,000 - уже секунды или минуты.

O(log n): деление пополам

**O(log n)** - на каждом шаге отбрасываем половину данных. Растёт очень медленно: при n = 1 000 000 нужно ~20 шагов.

**Где встречается O(log n):**

• Бинарный поиск
• Операции в сбалансированных деревьях (BST, AVL)
• Поиск в куче (Heap)
• Некоторые алгоритмы деления (divide & conquer)

**Правило:** если на каждой итерации данные уменьшаются **вдвое** - это O(log n).

O(n log n): Оптимальная сортировка

**O(n log n)** - золотой стандарт для сортировки. Лучше чем O(n²), но хуже O(n).

**Факт:** доказано, что сортировка сравнениями **не может** быть быстрее O(n log n). Это теоретический предел!

Сравнение сложностей

**От быстрого к медленному:**

**Цель:** стремиться к O(n log n) или лучше. O(n²) допустим для малых n (< 1000). O(2ⁿ) - только для очень малых n (< 20-30).

Шпаргалка Big O

• Big O - как растёт время при росте данных
• O(1) - константа, O(n) - линейно, O(n²) - квадратично
• O(log n) - деление пополам (бинарный поиск)
• O(n log n) - оптимальная сортировка
• Вложенные циклы → умножаем: O(n) × O(n) = O(n²)
• Игнорируем константы и младшие члены

Следующие темы

После этого урока понятно как измерять алгоритмы. Следующий шаг - понять, что кроме времени важна ещё и память.

• Пространственная сложность — Time vs Memory
• O(n²) сортировки — Bubble, Selection, Insertion
• Бинарный поиск — O(log n) на практике

Вопросы для размышления

• Вспомни код, который ты писал недавно - цикл, поиск, сортировка. Какая у него сложность по Big O? Можешь ли ты придумать способ улучшить его до следующего класса (например, с O(n²) до O(n log n))?

Связанные уроки

• prog-07-loops — Циклы - основная конструкция, определяющая сложность алгоритмов
• alg-02-space — Следующая тема: пространственная сложность как дополнение к временной
• ds-01-arrays — Первое практическое применение Big O - операции с массивами
• calc-01-sequences — Математика роста функций - прямая теоретическая основа нотации Big O
• comp-01-intro