В прошлом уроке мы научились записывать алгоритмы — словами, псевдокодом и блок-схемами. Это здорово: теперь можно описать любую последовательность действий так, чтобы её понял и человек, и компьютер. Но вот вопрос, который рано или поздно встаёт перед каждым разработчиком: если у нас два алгоритма, решающих одну и ту же задачу — как понять, какой из них лучше?

В разведке боем вы столкнулись именно с такой ситуацией. Два фрагмента кода, обе проверяют: есть ли число в коллекции? Один идёт циклом по List<int>, перебирая элемент за элементом. Другой вызывает HashSet<int>.Contains() — одну строчку. И HashSet оказался драматически быстрее. Не на 10%, не в два раза — а на порядки.

Но во сколько раз именно? И как мы это узнали без запуска кода?

Первый порыв — запустить оба варианта и замерить секундомером. Казалось бы, что может быть проще? Запустили — засекли — сравнили. Но тут начинаются проблемы. На вашем ноутбуке цикл пробежал за 50 миллисекунд, а на рабочем сервере — за 12. На ноутбуке коллеги — за 80. Утром тот же код работает за 30 мс, а вечером, когда Chrome решил съесть 8 гигабайт оперативки — за 200 мс. Данные разные, железо разное, загрузка системы разная — и каждый замер показывает новое число.

Получается, секундомер привязан к конкретному компьютеру, конкретному моменту и конкретным данным. Он не может ответить на главный вопрос: какой алгоритм в принципе быстрее? Нужен инструмент, который оценивает скорость алгоритма без привязки к железу, операционной системе и фазе луны. Такой инструмент существует — и называется он нотация Big O.

Прежде чем давать формальное определение, разберём идею на примере, который понятен каждому.

Представьте толстый бумажный словарь на 1000 страниц. Вам нужно найти слово «Оптимизация».

Способ первый: открыть страницу 1, прочитать все слова — нет нужного. Страница 2 — нет. Страница 3 — нет. И так далее, пока не найдёте. В худшем случае придётся перелистать все 1000 страниц (если слово на последней). А если словарь вырастет до 10 000 страниц — работы станет в 10 раз больше. Словарь вырос линейно — и время поиска выросло линейно.

Способ второй: открыть словарь ровно посередине. Видите букву «М». «Оптимизация» по алфавиту идёт позже — значит, левую половину можно выбросить. Берём правую, снова открываем посередине — «Р». Перелёт: «О» раньше, чем «Р» — выбрасываем правую часть. С каждым шагом область поиска сокращается вдвое. Для 1000 страниц хватит примерно 10 шагов. А для 10 000? Всего 14. Словарь вырос в 10 раз, а работы прибавилось всего на 4 шага.

Способ третий: представьте, что у вас есть волшебный указатель — вы заранее знаете: «Оптимизация — страница 547». Открыли — нашли. Одно действие. И совершенно неважно, сколько в словаре страниц — хоть миллион, хоть миллиард. Одно действие.

Три способа поиска — три принципиально разных скорости роста. Нотация Big O — это язык, на котором программисты описывают эту разницу. Первый способ — O(n). Второй — O(log n). Третий — O(1). Буква n обозначает размер входных данных — в нашем случае количество страниц в словаре.

Ключевой момент: Big O не говорит, сколько секунд займёт алгоритм. Она говорит, как изменится время, когда данных станет больше. Это как разница между «машина едет 80 км/ч» и «чем длиннее дорога, тем пропорционально дольше ехать». Первое — конкретный замер, второе — характер зависимости. Big O — про второе.

Ещё важная деталь: Big O отбрасывает константы и младшие члены. Если алгоритм делает 3n + 5 операций, Big O скажет просто O(n). Если 2n² + 100n + 42 — скажет O(n²). Почему? Потому что при огромных n именно старший член определяет поведение. Когда n = миллион, разница между n² и n² + 100n — доли процента, а вот разница между n и n² — в миллион раз. Теперь пройдёмся по каждому классу сложности и увидим его в живом C#-коде.

Начнём с самого приятного — O(1), или константное время. Алгоритм выполняет фиксированное количество операций, сколько бы данных ни было.

Допустим, у вас есть массив с ценами товаров в интернет-магазине, и нужно узнать цену третьего товара:

double[] prices = { 299.90, 1499.00, 549.50, 89.90, 3200.00 };

// Получаем цену третьего товара (индекс 2)
double thirdPrice = prices[2]; // 549.50

Одна операция. Компьютер точно знает, где в памяти лежит элемент с индексом 2 — он вычисляет адрес по формуле «начало массива + индекс * размер элемента» — и мгновенно прыгает туда. Массив может содержать 10 элементов или 10 миллионов — время доступа не изменится. Это и есть O(1): количество операций не зависит от размера данных.

Какие ещё операции работают за O(1)? Проверка количества элементов в списке — list.Count (список хранит счётчик, а не пересчитывает каждый раз). Получение значения из словаря по ключу — dict[key] (спасибо хеш-функции). Добавление элемента в конец списка — list.Add(item) (в среднем случае). Всё это мгновенные операции, и они остаются мгновенными при любом размере коллекции.

Следующий класс — O(n), или линейное время. Здесь время растёт прямо пропорционально количеству данных.

HR-отдел попросил найти максимальную зарплату среди сотрудников. Данные лежат в обычном несортированном списке, и никакой магии — придётся заглянуть в каждый элемент:

List<double> salaries = new List<double>
    { 45000, 72000, 58000, 91000, 63000 };

double maxSalary = salaries[0];

for (int i = 1; i < salaries.Count; i++)
{
    if (salaries[i] > maxSalary)
        maxSalary = salaries[i];
}

Console.WriteLine($"Максимальная зарплата: {maxSalary}");
// Максимальная зарплата: 91000

Мы прошли по каждому элементу ровно один раз. Пропустить ни один нельзя — вдруг самая большая зарплата окажется в самом конце? Если сотрудников 100 — будет ~100 сравнений. Если 10 000 — будет ~10 000 сравнений. Удвоили список — удвоилось время. Зависимость линейная, поэтому записываем: O(n), где n — количество элементов.

Тот самый поиск числа циклом по List<int> из разведки боем — тоже O(n). В худшем случае цикл обойдёт весь список от начала до конца. А HashSet.Contains() работает за O(1) благодаря хеш-таблице под капотом. Вот вам и ответ на вопрос «во сколько раз быстрее»: при миллионе элементов разница между одной операцией и миллионом операций — это разница в миллион раз. Не в два, не в десять — в миллион. Теперь задачка потруднее. Руководитель просит проверить, нет ли в списке сотрудников однофамильцев. У вас список имён, и нужно сравнить каждого с каждым:

List<string> employees = new List<string>
{
    "Иванов", "Петров", "Сидоров", "Козлов", "Иванов"
};

for (int i = 0; i < employees.Count; i++)
{
    for (int j = i + 1; j < employees.Count; j++)
    {
        if (employees[i] == employees[j])
            Console.WriteLine($"Однофамильцы: {employees[i]} " +
                $"(позиции {i} и {j})");
    }
}
// Однофамильцы: Иванов (позиции 0 и 4)

Видите два вложенных цикла? Внешний идёт по каждому сотруднику, внутренний — сравнивает его со всеми последующими. При 5 сотрудниках это 10 сравнений — мелочь. Но посмотрим на масштабе:

100 сотрудников — около 5 000 сравнений. Терпимо.

1 000 сотрудников — около 500 000 сравнений. Уже ощутимо.

10 000 сотрудников — около 50 000 000 сравнений. Программа начинает подтормаживать.

100 000 сотрудников — около 5 000 000 000 сравнений. Можно идти заваривать чай.

Увеличили список в 10 раз — работа выросла в 100 раз. Увеличили в 100 раз — работа выросла в 10 000 раз. Это O(n²), или квадратичное время. Два вложенных цикла, каждый из которых зависит от размера данных — классический признак квадратичной сложности. Именно поэтому такие алгоритмы становятся неприемлемо медленными на больших объёмах.

Кстати, задачу с однофамильцами можно решить за O(n) — достаточно воспользоваться HashSet<string> и проверять, встречалось ли имя раньше, по мере прохода. Один цикл вместо двух вложенных — и разница колоссальная. Вот что значит выбрать правильный алгоритм.

И наконец, самый элегантный класс — O(log n), или логарифмическое время. Помните поиск слова в словаре, когда мы открывали посередине и каждый раз отбрасывали половину? Этот приём называется бинарный поиск, и он работает только с отсортированными данными. Зато — невероятно быстро.

Допустим, у вас есть отсортированный массив ID сотрудников, и нужно найти конкретный:

int[] sortedIds = { 101, 205, 308, 417, 523, 639, 742, 856, 961 };
int target = 639;

int left = 0;
int right = sortedIds.Length - 1;

while (left <= right)
{
    int mid = (left + right) / 2;

    if (sortedIds[mid] == target)
    {
        Console.WriteLine($"Найден на позиции {mid}");
        break;
    }
    else if (sortedIds[mid] < target)
        left = mid + 1;   // ищем в правой половине
    else
        right = mid - 1;  // ищем в левой половине
}
// Найден на позиции 5

На каждом шаге мы делим область поиска пополам. Начали с 9 элементов — после первого шага осталось 4, после второго — 2, после третьего — 1. Максимум 4 шага для 9 элементов.

А теперь — числа, от которых захватывает дух. Для тысячи элементов бинарный поиск сделает максимум 10 шагов. Для миллиона — 20. Для миллиарда — всего 30. Миллиард элементов — тридцать шагов. Логарифм растёт настолько медленно, что даже при космических объёмах данных алгоритм остаётся молниеносным.

Именно O(log n) лежит в основе поиска по базам данных, по файловым системам, по сбалансированным деревьям — везде, где нужно быстро найти иголку в стоге сена.

Чтобы разница стала совсем наглядной, сведём всё в таблицу. Посмотрите, как ведут себя разные классы сложности при росте данных:

Один и тот же миллион элементов: O(1) даже не заметит — одна операция. O(log n) управится за 20 шагов — быстрее, чем вы моргнёте. O(n) прокрутит миллион операций — терпимо, современный процессор справится за доли секунды.

А O(n²)? Триллион операций. При скорости миллиард операций в секунду — это тысяча секунд, почти 17 минут. На одну-единственную проверку дубликатов. А если данных станет 10 миллионов? 10¹⁴ операций — это уже больше трёх лет непрерывной работы. Три года на задачу, которую O(n)-алгоритм решает за 10 секунд.

Вот почему выбор алгоритма — это не каприз перфекциониста и не преждевременная оптимизация. Это вопрос: «Будет ли программа вообще работать, когда к ней придут настоящие пользователи с настоящими данными?». Два алгоритма могут давать одинаковый результат, но один справится за доли секунды, а другой не доживёт до ответа.

Нотация Big O — способ описать, как растёт время работы алгоритма при увеличении входных данных. Она показывает не конкретное время в секундах, а характер роста: удвоится ли время, вырастет в четыре раза или останется прежним. Big O отбрасывает константы и младшие члены — при больших объёмах данных важен только старший член.

O(1) — константное время. Количество операций не зависит от размера данных. Пример: доступ к элементу массива по индексу, получение значения из словаря по ключу, проверка list.Count.

O(log n) — логарифмическое время. Область поиска сокращается вдвое на каждом шаге. Миллиард элементов — около 30 шагов. Пример: бинарный поиск в отсортированном массиве.

O(n) — линейное время. Каждый элемент обрабатывается ровно один раз. Удвоили данные — удвоилось время. Пример: поиск максимума в несортированном списке.

O(n²) — квадратичное время. Два вложенных цикла по одним данным. Увеличили входные данные в 10 раз — время выросло в 100 раз. Пример: поиск дубликатов попарным сравнением.

Big O описывает верхнюю границу — худший случай. В реальности алгоритм может отработать быстрее, но при оценке производительности мы всегда закладываемся на максимальную нагрузку. Выбор алгоритма с правильной сложностью — это не оптимизация ради оптимизации, а вопрос работоспособности программы на реальных данных.