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

Нотация «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]);
      }
  }

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