Перейти на PRO

Что такое нотация «O» большое (Big O)?

Тип вопроса: Алгоритмы и структуры данных Вероятность: 25% Категория: C/C++ Разработчик

Ответ

Нотация «O» большое (Big O notation) — это математическая асимптотическая запись, используемая в информатике для описания верхней границы временной или пространственной сложности алгоритма в худшем случае при росте размера входных данных n. Она позволяет абстрактно оценить, как алгоритм будет масштабироваться.

Ключевые принципы:

  • Игнорирует константные множители и младшие слагаемые. O(5n + 100) упрощается до O(n).
  • Фокусируется на порядке роста при n → ∞.
  • Описывает худший сценарий, что гарантирует, что алгоритм не будет работать медленнее этой оценки.

Распространённые классы сложности с примерами на C++:

  • O(1) — Константная сложность. Время выполнения не зависит от размера входных данных.

    // Доступ к элементу массива по индексу
int getElement(const std::vector<int>& vec, size_t index) {
    return vec[index]; // O(1)
}

  • O(log n) — Логарифмическая сложность. Характерна для алгоритмов, делящих задачу пополам на каждом шаге.

    // Бинарный поиск в отсортированном массиве
int binarySearch(const std::vector<int>& vec, int target) {
    int left = 0, right = vec.size() - 1;
    while (left <= right) { // O(log n)
        int mid = left + (right - left) / 2;
        if (vec[mid] == target) return mid;
        if (vec[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

  • O(n) — Линейная сложность. Время выполнения прямо пропорционально n.

    // Линейный поиск или обход массива
int findMax(const std::vector<int>& vec) {
    int maxVal = vec[0];
    for (int num : vec) { // O(n)
        if (num > maxVal) maxVal = num;
    }
    return maxVal;
}

  • O(n log n) — Линейно-логарифмическая сложность. Часто встречается в эффективных алгоритмах сортировки.

    // Сортировка слиянием (merge sort) или быстрая сортировка (quicksort) в среднем случае.
std::vector<int> vec = {...};
std::sort(vec.begin(), vec.end()); // O(n log n)

  • O(n²) — Квадратичная сложность. Характерна для простых алгоритмов с вложенными циклами.

    // Сортировка пузырьком (bubble sort)
for (size_t i = 0; i < vec.size(); ++i) {        // O(n²)
    for (size_t j = 0; j < vec.size() - i - 1; ++j) {
        if (vec[j] > vec[j+1]) std::swap(vec[j], vec[j+1]);
    }
}

Выбор алгоритма с оптимальной асимптотической сложностью критически важен для обработки больших объёмов данных.

Ответ 18+ 🔞

А, слушай, вот эта вся хуйня с «O» большим — это, по сути, такой способ на пальцах объяснить, насколько твой алгоритм будет тормозить, когда данных станет овердохуища. Представь, что ты пытаешься найти одного человека в толпе. Если ты знаешь, где он стоит (по индексу) — это мгновенно, O(1). А если ты должен пройти и посмотреть на каждого — это уже O(n), и чем толпа больше, тем дольше.

Главные фишки этой нотации:

  • Ей да похуй на мелкие константы. O(9999n + 1000000) для неё — всё равно что просто O(n). Она смотрит на картину маслом, когда n летит в бесконечность.
  • Она всегда показывает худший случай. То есть, если она говорит O(n²), то будь уверен — быстрее, чем квадратично, в самом поганом раскладе не будет. Доверия ебать ноль к оптимистичным сценариям.

Вот основные градации, от лучшего к худшему, с примерами на C++:

  • O(1) — Константная. Алгоритму в рот меня чих-пых, сколько там данных. Время одно и то же.

    // Достал элемент из массива по индексу — и всё.
int getElement(const std::vector<int>& vec, size_t index) {
    return vec[index]; // O(1)
}

  • O(log n) — Логарифмическая. Умная жопа. Задача на каждом шаге делится пополам. Растёт оч-чень медленно.

    // Бинарный поиск. Отсортированный массив? Дели пополам, отбрасывай ненужную часть — красота.
int binarySearch(const std::vector<int>& vec, int target) {
    int left = 0, right = vec.size() - 1;
    while (left <= right) { // O(log n)
        int mid = left + (right - left) / 2;
        if (vec[mid] == target) return mid;
        if (vec[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

  • O(n) — Линейная. Чем больше данных, тем ровно во столько же раз дольше работа. Прямая зависимость, без сюрпризов.

    // Прошёлся по всему массиву один раз — вот и O(n).
int findMax(const std::vector<int>& vec) {
    int maxVal = vec[0];
    for (int num : vec) { // O(n)
        if (num > maxVal) maxVal = num;
    }
    return maxVal;
}

  • O(n log n) — Линейно-логарифмическая. Частый гость в эффективных сортировках. Хуже, чем линейная, но ещё терпимо, в отличие от квадратичной.

    // std::sort внутри себя обычно так и работает. Лучше, чем O(n²), это точно.
std::vector<int> vec = {...};
std::sort(vec.begin(), vec.end()); // O(n log n)

  • O(n²) — Квадратичная. Вот тут начинается ёперный театр. Каждый элемент нужно сравнить с каждым. На маленьких данных — ладно, но как n подрастёт — терпения ноль ебать, всё зависнет.

    // Пузырёк, классика жанра для учебников и для того, чтобы никогда так не делать.
for (size_t i = 0; i < vec.size(); ++i) {        // O(n²)
    for (size_t j = 0; j < vec.size() - i - 1; ++j) {
        if (vec[j] > vec[j+1]) std::swap(vec[j], vec[j+1]);
    }
}

Так что суть в чём: если пишешь что-то для реальной работы, а не для лабораторной на пять элементов, э бошка думай над этой сложностью. Выбрал O(n²) вместо O(n log n) для миллиона записей — и всё, можно идти пить чай. Надолго.

© ХакСобесов, 2026
support@hacksobesov.com