Big O — это способ описать:
🔹 как быстро растёт время работы алгоритма,
🔹 когда растёт количество данных.
Важно:
- это не секунды
- это не про конкретный компьютер
- это про рост сложности
Простейший пример
Допустим, у тебя есть N заказов.
❓ Вопрос:
Если заказов станет в 2 раза больше,
время работы станет:
- в 2 раза?
- в 4 раза?
- в 10 раз?
Вот это и описывает Big O.
O(n) — линейная сложность
📌 Что значит
Время растёт прямо пропорционально количеству элементов
Пример из твоего кода
$topUser = null;
$maxOrders = 0;
foreach ($ordersByUsers as $user => $stats) {
if ($stats['orders'] > $maxOrders) {
$maxOrders = $stats['orders'];
$topUser = $user;
}
}Что происходит
- 1 пользователь → 1 проверка
- 10 пользователей → 10 проверок
- 1000 пользователей → 1000 проверок
👉 Каждый элемент обрабатывается ровно один раз
💡 Это и есть O(n).
Визуально
| Кол-во элементов | Операций |
|---|---|
| 1 | 1 |
| 10 | 10 |
| 100 | 100 |
| 1000 | 1000 |
📈 Прямая линия.
Пример: Бинарный поиск
Сколько времени сэкономит его применение? В первом варианте мы последовательно проверяли каждое число, одно за другим. Если список состоит из 100 чисел, может потребоваться до 100 попыток. Для списка из 4 миллиардов чисел потребует я о 4 миллиардов попыток. Таким образом, максимальное количество попыток совпадает с размером списка. Такое время выполнения называется линейным.
С бинарным поиском дело обстоит иначе. Если список остоит з 100 элементов, потребуется не более 7 попыток. Для списка из 4 миллиардов элментов потребуется не более 32 попыток. Впечатляет, верно? Бинарный поиск выполняется за логарифмическое время. В следующей таблице приводится краткая сводка результатов.
«О-большое» описывает, насколько быстро работает алгоритм.
Боб проводит бинарный поиск с 1 миллиардом элементов, и на это уходит 30 мс (log2 1 ООО ООО ООО равен приблизительно 30). «32 мс! – думает Боб. – Бинарный поиск в 15 раз быстрее простого, потому что простой поиск для 100 элементов занял 100 мс, а бинарный поиск занял 7 мс. Значит, простой поиск займет 30 х 15 = 450 мс, верно? Гораздо меньше отведенных 10 секунд~. И Боб выбирает простой поиск. Верен ли его выбор?
Нет, Боб ошибается. Глубоко ошибается. Время выполнения для простого поиска с 1 миллиардом элементов составит 1 миллиард миллисекунд, а это 11 дней! Проблема в том, что время выполнения для бинарного и простого поиска растет с разной скоростью.
Бот почему недостаточно знать, сколько времени должен работать алгоритм, – необходимо знать, как возрастает время выполнения с ростом размера списка. Здесь-то вам и пригодится “О-большое”.
«О-большое» описывает, насколько быстро работает алгоритм. Предположим, имеется список размера n. Простой поиск должен проверить каждый элемент, поэтому ему придется выполнить n операций. Время выполнения О-большое» имеет вид О(n).
Постойте, но где же секунды? А их здесь нет – “О-большое” не сообщает скорость
в секундах, а позволяет сравнить количество операций . Оно указывает, насколько
быстро возрастает время выполнения алгоритма.
«О-большое» определяет время выполнения в худшем случае
Предположим, вы используете простой поиск для поиска фамилии в телефонной книге. Вы знаете, что простой поиск выполняется за время О(n), то есть в худшем случае вам придется просмотреть каждую без исключения запись в телефонной книге. Но представьте , что искомая фамилия начинается на букву “А” и тот человек стоит на самом первом месте в вашей телефонной книге. В общем, вам не пришлось просматривать все записи – вы нашли нужную фамилию с первой попытки. Отработал ли алгоритм за время О(n)? А может, он занял время 0(1), потому что результат был получен с первой попытки? Простой поиск все равно выполняется за время О(n) . Просто в данном случае вы нашли нужное значение моментально; это лучший возможный случай. Однако “О-большое” описывает худший возможный случай. Фактически вы утверждаете, что в худшем случае придется просмотреть каждую запись в телефонной книге по одному разу. Это и есть время О(n). И это дает определенные гарантии – вы знаете, что простой поиск никогда не будет работать медленнее О(п).
Типичные примеры «О-большого»
Ниже перечислены пять разновидностей «О-большого», которые будут встречаться вам особенно часто, в порядке убывания скорости выполнения:
- O(log n), или логарифмическое время. Пример: бинарный поиск.
- О(n), или линейное время. Пример: простой поиск.
- О(n * log n). Пример: эффективные алгоритмы сортировки (быстрая сортировка).
- О(n2). Пример: медленные алгоритмы сортировки (сортировка выбором).
- О(n!)(n-факториал). Пример: очень медленные алгоритмы (задача о коммивояжере).
O(n log n) — сортировка
Теперь возьмём сортировку:
uasort($ordersByUsers, function($a, $b) {
return $b['orders'] <=> $a['orders'];
});
$topUser = array_key_first($ordersByUsers);
$topOrders = $ordersByUsers[$topUser]['orders'];Почему не O(n)?
Потому что сортировка:
- сравнивает элементы между собой
- делает это много раз
Большинство сортировок работают как:
n * log2(n)Пример чисел
| n | log2(n) | n log n |
|---|---|---|
| 10 | ~3 | 30 |
| 100 | ~7 | 700 |
| 1000 | ~10 | 10 000 |
| 100 000 | ~17 | 1 700 000 |
📈 Это растёт быстрее, чем O(n).
Почему log вообще появляется
Потому что алгоритм:
- делит данные пополам
- сортирует части
- объединяет
(merge sort, quick sort, timsort и т.д.)
Почему «найти максимум» — O(n), а не O(n log n)
❌ Плохой подход
uasort($ordersByUsers, function($a, $b) {
return $b['orders'] <=> $a['orders'];
});
$topUser = array_key_first($ordersByUsers);
$topOrders = $ordersByUsers[$topUser]['orders'];→ сортируем ВСЁ
→ хотя нужен один элемент
⏱️ O(n log n)
Правильный подход
$topUser = null;
$maxOrders = 0;
foreach ($ordersByUsers as $user => $stats) {
if ($stats['orders'] > $maxOrders) {
$maxOrders = $stats['orders'];
$topUser = $user;
}
}⏱️ O(n)
Ключевая мысль
Если нужен максимум / минимум — НЕ сортируй.
Сортировка нужна только, если:
- важен порядок ВСЕХ элементов
- нужен топ-N (несколько элементов)
Что быстрее на практике
| Кол-во пользователей | O(n) | O(n log n) |
|---|---|---|
| 100 | незаметно | незаметно |
| 10 000 | быстро | ощутимо |
| 1 000 000 | нормально | больно 😬 |
Простая аналогия (очень важно)
Найти самого высокого человека в комнате
❌ Плохой вариант:
- выстроить всех по росту
- взять последнего
✅ Хороший вариант:
- пройтись
- запомнить максимум
Как вообще считать O(n), O(n²) и т.д.
Главное правило – Считаем, сколько раз выполняется код при росте данных.
Не «формулы», не «страшные буквы», а сколько раз мы что-то делаем.
1️⃣ Что такое n
n — это размер входных данных.
В твоей задаче:
n= количество слов
Если:
- 10 слов →
n = 10 - 10 000 слов →
n = 10 000
2️⃣ Что значит O(n)
Пример:
foreach ($words as $word) {
echo $word;
}Если:
- 10 слов → 10 операций
- 100 слов → 100 операций
- 10 000 слов → 10 000 операций
📈 Количество операций растёт прямо пропорционально n
👉 Это O(n)
3️⃣ Почему in_array — это тоже O(n)
in_array($word, $uniqueWords)PHP:
- проверяет 1-й элемент
- потом 2-й
- потом 3-й
- …
- пока не найдёт или не закончится массив
Если в $uniqueWords:
- 5 элементов → до 5 сравнений
- 5 000 элементов → до 5 000 сравнений
👉 значит O(n)
4️⃣ Теперь самое важное: O(n) * O(n) = O(n²)
Смотри на код:
foreach ($words as $word) { // ← выполняется n раз
if (!in_array($word, $uniqueWords)) { // ← внутри, до n проверок
$uniqueWords[] = $word;
}
}Разбор по шагам
foreach— n раз- Внутри каждый раз
in_array— до n проверок
👉 Итого:
n × n = n²5️⃣ Числовой пример (очень важно)
| Кол-во слов | Операций |
|---|---|
| 10 | 100 |
| 100 | 10 000 |
| 1 000 | 1 000 000 |
| 10 000 | 100 000 000 |
Вот почему такие вещи внезапно тормозят.
6️⃣ Почему isset($array[$key]) — O(1)
isset($uniqueWords[$word])PHP:
- вычисляет хеш ключа
- сразу прыгает в нужную ячейку
⏱ одна операция, не зависит от размера массива.
👉 это O(1)
7️⃣ Как быстро определять сложность (шпаргалка)
- Один цикл = O(n)
- Цикл внутри цикла = O(n²)
- Цикл + поиск через
in_array= O(n²)
8️⃣ Самый важный практический совет
Не пытайся высчитывать формулы.
Просто отвечай на вопрос: “Сколько раз это выполнится при большом количестве данных?”
Если ответ:
- «примерно столько же» → O(n)
- «в n раз больше» → O(n²)
- «не зависит от размера» → O(1)
Резюме
- O(n) — один проход
- O(n log n) — сортировка
- если нужен максимум → O(n)
- сортировка ≠ поиск
