Описание тега big-o

Обозначение Big-O используется для представления асимптотических оценок сверху. Это позволяет человеку увидеть, потребуются ли годы или секунды для решения проблемы на современном компьютере.

В информатике он чаще всего используется, когда говорят о временной сложности алгоритмов, но также может относиться к требуемой памяти.

Например, линейный поиск в несортированном массиве размера N равен O (N). Если мы помещаем элементы первыми в хеш-таблицу, используемое пространство составляет O (N) (Точнее, Theta (N)), но время поиска составляет O (1) в среднем случае.

Следует отметить, что Big-O представляет собой только верхнюю границу функции. Следовательно, функция O (N) также будет O (NlogN), O (N²), O (N!) И т. Д. Во многих случаях Big-O используется неточно, и вместо него следует использовать Big-Theta.

Если сложность задается рекуррентным соотношением, анализ часто можно провести с помощью основной теоремы.

Свойства

• Суммирование
  O (f (n)) + O (g (n)) -> O (max (f (n), g (n)))
  Например: O(n^2) + O(n) = O(п ^2)

• Умножение на положительную константу
  O(c * f(n)) -> O(f(n))
  Например: O(1000 * n^2) = O(n^2)

• Умножение
  O(f(n)) * O(g(n)) -> O(f(n) * g(n))
  Например: O(n^2) * O(n) = O(n^2 * п) = O (п ^3)

• Транзитивность
  f(n) = O(g(n)) и g(n) = O(h(n)), тогда f(n) = O(h(n))
  

Группы Big-O

Сложность | Примеры алгоритмов                               
-------------------------------------------------- ----------------
- О (Н!)       | Получить все перестановки из N элементов
- O(2^N)      | Итерации по всем подмножествам из N элементов
- O(N^3)      | Вычисление всех троек из N элементов
- O(N^2)      | Перечисляя все пары из N элементов, вставьте сортировку
- O(NLog(N))  | Быстрая сортировка, сортировка слиянием
- O(N)        | Получение минимального, максимального, среднего, итерация по N элементам
- O (Лог (N)) | Бинарный поиск
- О (1)        | Получение элемента по индексу в массиве