Что такое o большое
Перейти к содержимому

Что такое o большое

Big O

Примечание. Сокращенный перевод, скорее пересказ своими словами.
UPD: как отметили в комментариях, примеры не идеальны. Автор не ищет лучшее решение задачи, его цель объяснить сложность алгоритмов «на пальцах».

Big O нотация нужна для описания сложности алгоритмов. Для этого используется понятие времени. Тема для многих пугающая, программисты избегающие разговоров о «времени порядка N» обычное дело.

Если вы способны оценить код в терминах Big O, скорее всего вас считают «умным парнем». И скорее всего вы пройдете ваше следующее собеседование. Вас не остановит вопрос можно ли уменьшить сложность какого-нибудь куска кода до n log n против n^2.

Структуры данных

Выбор структуры данных зависит от конкретной задачи: от вида данных и алгоритма их обработки. Разнообразные структуры данных (в .NET или Java или Elixir) создавались под определенные типы алгоритмов.

Часто, выбирая ту или иную структуру, мы просто копируем общепринятое решение. В большинстве случаев этого достаточно. Но на самом деле, не разобравшись в сложности алгоритмов, мы не можем сделать осознанный выбор. К теме структур данных можно переходить только после сложности алгоритмов.

Здесь мы будем использовать только массивы чисел (прямо как на собеседовании). Примеры на JavaScript.

Начнем с самого простого: O(1)

Возьмем массив из 5 чисел:

const nums = [1,2,3,4,5];

Допустим надо получить первый элемент. Используем для это индекс:

const nums = [1,2,3,4,5]; const firstNumber = nums[0];

Насколько это сложный алгоритм? Можно сказать: «совсем не сложный — просто берем первый элемент массива». Это верно, но корректнее описывать сложность через количество операций, выполняемых для достижения результата, в зависимости от ввода (операций на ввод).

Другими словами: насколько возрастет кол-во операций при увеличении кол-ва входных параметров.

В нашем примере входных параметров 5, потому что в массиве 5 элементов. Для получения результата нужно выполнить одну операцию (взять элемент по индексу). Сколько операций потребуется если элементов массива будет 100? Или 1000? Или 100 000? Все равно нужна только одна операция.

Т.е.: «одна операция для всех возможных входных данных» — O(1).

O(1) можно прочитать как «сложность порядка 1» (order 1), или «алгоритм выполняется за постоянное/константное время» (constant time).

Вы уже догадались что O(1) алгоритмы самые эффективные.

Итерации и «время порядка n»: O(n)

Теперь давайте найдем сумму элементов массива:

const nums = [1,2,3,4,5]; let sum = 0; for(let num of nums)

Опять зададимся вопросом: сколько операций на ввод нам потребуется? Здесь нужно перебрать все элементы, т.е. операция на каждый элемент. Чем больше массив, тем больше операций.

Используя Big O нотацию: O(n), или «сложность порядка n (order n)». Так же такой тип алгоритмов называют «линейными» или что алгоритм «линейно масштабируется».

Анализ

Можем ли мы сделать суммирование более эффективным? В общем случае нет. А если мы знаем, что массив гарантированно начинается с 1, отсортирован и не имеет пропусков? Тогда можно применить формулу S = n(n+1)/2 (где n последний элемент массива):

const sumContiguousArray = function(ary) < //get the last item const lastItem = ary[ary.length - 1]; //Gauss's trick return lastItem * (lastItem + 1) / 2; >const nums = [1,2,3,4,5]; const sumOfArray = sumContiguousArray(nums);

Такой алгоритм гораздо эффективнее O(n), более того он выполняется за «постоянное/константное время», т.е. это O(1).

Фактически операций не одна: нужно получить длину массива, получить последний элемент, выполнить умножение и деление. Разве это не O(3) или что-нибудь такое? В Big O нотации фактическое кол-во шагов не важно, важно что алгоритм выполняется за константное время.

Алгоритмы с константным временем это всегда O(1). Тоже и с линейными алгоритмами, фактически операций может быть O(n+5), в Big O нотации это O(n).

Не самые лучшие решения: O(n^2)

Давайте напишем функцию которая проверяет массив на наличие дублей. Решение с вложенным циклом:

const hasDuplicates = function (num) < //loop the list, our O(n) op for (let i = 0; i < nums.length; i++) < const thisNum = nums[i]; //loop the list again, the O(n^2) op for (let j = 0; j < nums.length; j++) < //make sure we're not checking same number if (j !== i) < const otherNum = nums[j]; //if there's an equal value, return if (otherNum === thisNum) return true; >> > //if we're here, no dups return false; > const nums = [1, 2, 3, 4, 5, 5]; hasDuplicates(nums);//true

Мы уже знаем что итерирование массива это O(n). У нас есть вложенный цикл, для каждого элемента мы еще раз итерируем — т.е. O(n^2) или «сложность порядка n квадрат».

Алгоритмы с вложенными циклами по той же коллекции всегда O(n^2).

«Сложность порядка log n»: O(log n)

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

Здесь вложенный цикл используется для поиска заданного элемента в массиве. Поиск элемента в массиве, при определенных условиях, можно оптимизировать — сделать лучше чем линейная O(n).

Пускай массив будет отсортирован. Тогда мы сможем использовать алгоритм «бинарный поиск»: делим массив на две половины, отбрасываем не нужную, оставшуюся опять делим на две части и так пока не найдем нужное значение. Такой тип алгоритмов называется «разделяй и влавствуй» Divide and Conquer.

бинарный поиск

Этот алгоритм основан на логарифме.

Быстрый обзор логарифмов

Рассмотрим пример, чему будет равен x?

Нужно взять кубический корень от 8 — это будет 2. Теперь посложнее

С использованием логарифма задачу можно записать так

«логарифм по основанию 2 от 512 равен x». Обратите внимание «основание 2», т.е. мы мыслим двойками — сколько раз нужно перемножить 2 что бы получить 512.

В алгоритме «бинарный поиск» на каждом шаге мы делим массив на две части.

Мое дополнение. Т.е. в худшем случае делаем столько операций, сколько раз можем разделить массив на две части. Например, сколько раз мы можем разделить на две части массив из 4 элементов? 2 раза. А массив из 8 элементов? 3 раза. Т.е. кол-во делений/операций = log2(n) (где n кол-во элементов массива).

Получается, что зависимость кол-ва операций от кол-ва элементов ввода описывается как log2(n)

Таким образом, используя нотацию Big O, алгоритм «бинарный поиск» имеет сложность O(log n).

Улучшим O(n^2) до O(n log n)

Вернемся к задачке проверки массива на дубли. Мы перебирали все элементы массива и для каждого элемента еще раз делали перебор. Делали O(n) внутри O(n), т.е. O(n*n) или O(n^2).

Мы можем заменить вложенный цикл на бинарный поиск*. Т.е. у нас остается перебор всех элементов O(n), внутри делаем O(log n). Получается O(n * log n), или O(n log n).

const nums = [1, 2, 3, 4, 5]; const searchFor = function (items, num) < //use binary search! //if found, return the number. Otherwise. //return null. We'll do this in a later chapter. >const hasDuplicates = function (nums) < for (let num of nums) < //let's go through the list again and have a look //at all the other numbers so we can compare if (searchFor(nums, num)) < return true; >> //only arrive here if there are no dups return false; >

* ВНИМАНИЕ, во избежание Импринтинга. Использовать бинарный поиск для проверки массива на дубли — плохое решение. Здесь лишь показывается как в терминах Big O оценить сложность алгоритма показанного в листинге кода выше. Хороший алгоритм или плохой — для данной заметки не важно, важна наглядность.

Мышление в терминах Big O

  • Получение элемента коллекции это O(1). Будь то получение по индексу в массиве, или по ключу в словаре в нотации Big O это будет O(1)
  • Перебор коллекции это O(n)
  • Вложенные циклы по той же коллекции это O(n^2)
  • Разделяй и властвуй (Divide and Conquer) всегда O(log n)
  • Итерации которые используют Divide and Conquer это O(n log n)
  • big-o notation
  • алгоритмы
  • javascript
  • структуры данных
  • сложность алгоритма
  • сложность
  • бинарный поиск
  • JavaScript
  • Программирование
  • Алгоритмы

«О» большое — простое объяснение с картинками

Бью Карнес — разработчик, ведущий YouTube-канал сайта freeCodeCamp.org, — в своей статье «Big O Notation — Simply explained with illustrations and video» попытался простыми словами объяснить нотацию большого «О».

Нотация «О» большое используется для выражения скорости алгоритма. Это важно при оценке как чужих алгоритмов, так и своих собственных. В этой статье я объясню, что такое «О» большое, а также приведу список наиболее часто встречающихся значений большого «О» и соответствующих этим значениям алгоритмов.

Время работы алгоритмов растет с разной скоростью

У моего сына Иуды есть много игрушек. Их просто миллиард! Даже удивительно, как быстро ребенок может собрать такое количество игрушек, если он первый внук для обеих ветвей семейного древа.

В общем, у Иуды проблема. Когда к нему приходят друзья и хотят поиграть с какой-то определенной игрушкой, ее поиски могут занять целую вечность. Поэтому ему нужен алгоритм поиска, который помог бы найти нужную игрушку как можно быстрее. Он пытается выбрать между двумя разными алгоритмами: простым и двоичным.

Выбранный алгоритм должен быть и точным, и быстрым. С одной стороны, двоичный поиск быстрее. А у Иуды зачастую бывает лишь 30 секунд на поиски — пока его другу не станет слишком скучно искать игрушку. С другой стороны, алгоритм простого поиска легче написать, и шансы сделать что-то неверно гораздо меньше. Ведь если друг найдет баги в его коде, это будет очень огорчительно! Чтобы подойти к делу с максимальной точностью, Иуда решает засечь время, за которое каждый из алгоритмов справится со списком из ста игрушек.

Давайте предположим, что проверка одной игрушки занимает 1мс. Если Иуде придется проверить все 100 игрушек путем простого поиска, это займет 100мс. С другой стороны, применяя двоичный поиск, нужно проверить всего 7 игрушек (log2 100 это примерно 7, мы здесь не будем вдаваться в точную математику), а значит, на это уйдет 7мс.

Но на самом деле в списке миллиард игрушек. Сколько времени будет работать алгоритм простого поиска, обрабатывая такой список? А сколько времени понадобится алгоритму двоичного поиска?

Время работы простого и двоичного поиска

Время работы простого и двоичного поиска со списком из 100 элементов

Иуда запускает двоичный поиск со списком из 1 млрд. игрушек и на работу этого алгоритма уходит 30мс (log2 1000000000 примерно равен 30). «32мс! — думает он. — Сколько же времени понадобится при простом поиске? Двоичный поиск примерно в 15 раз быстрее простого, ведь алгоритму простого поиска понадобилось 100мс на список из 100 элементов, а алгоритму двоичного поиска — только 7мс. Значит, простой поиск со списком из 1 млрд. элементов займет 30мс*15 = 450мс, верно? Это намного меньше 30 секунд, за которые мой друг успеет устать». И Иуда решает воспользоваться алгоритмом простого поиска. Но был ли это правильный выбор?

Нет. Оказалось, что Иуда ошибся и, возможно, потерял своего друга навсегда. Время работы алгоритма простого поиска со списком из 1 млрд. элементов это не 450мс, а 1млрд. миллисекунд, т. е., 11 дней! Дело в том, что время работы двоичного и простого поиска возрастает не одинаково.

Как возрастает время работы алгоритмов

Время работы растет с разной скоростью! По мере увеличения количества элементов время работы двоичного поиска будет понемногу расти, но при этом время работы простого поиска возрастает очень сильно. То есть, когда число элементов в списке возрастает, двоичный поиск внезапно становится намного быстрее простого.

Так что Иуда ошибся, предполагая, что двоичный поиск всегда в 15 раз быстрее простого. Если брать список с 1 миллиардом элементов, двоичный поиск будет уже примерно в 33 миллиона раз быстрее простого.

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

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

Где же, собственно, время? Где секунды? Здесь их нет. «О» большое не сообщает вам скорость в секундах. Эта нотация позволяет вам сравнивать количество необходимых операций. Она говорит вам о том, как быстро возрастает скорость работы алгоритма.

Давайте рассмотрим еще один пример. Двоичному поиску для проверки списка из n элементов нужно осуществить log n операций. Каково время работы алгоритма, записанное в нотации «О» большого? O(log n). В общем, принцип записи следующий:

Нотация

Эта запись сообщает вам количество операций, которое осуществит алгоритм. Называется все это нотацией ««О» большое», потому что перед количеством операций ставится заглавная буква «О».

«О» большое описывает количество операций при наихудшем сценарии

Поиск пользователей

Предположим, вы ищете пользователя в своей базе данных и при этом применяете алгоритм простого поиска. Вы знаете, что его скорость — O(n), то есть, в наихудшем случае вашему алгоритму придется проверить каждого пользователя в вашей базе данных. Но допустим, вы ищете пользователя с именем aardvark213, а он стоит первым в списке. Вашему алгоритму не придется проверять каждый элемент списка, потому что он найдет нужного пользователя с первой попытки. Итак, время, которое потребовалось алгоритму, это O(n) или O(1)? Ведь он нашел нужного пользователя с первой же попытки?

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

Самые распространенные варианты «О» большого

Вот пять вариантов «О» большого, которые встречаются чаще всего. Они отсортированы от самого быстрого к самому медленному:

  • O(log n) — логарифмическое время. Пример: двоичный поиск.
  • O(n) — линейное время. Пример: простой поиск.
  • O(n * log n). Пример: быстрый алгоритм сортировки, такой как quicksort (быстрая сортировка).
  • O(n2) — квадратичное время. Пример: медленный алгоритм сортировки, такой как сортировка выбором.
  • O(n!) — факториальное время. Пример: очень медленный алгоритм, такой как в задаче коммивояжера.

Визуализация разного времени в нотации «О» большого

Сетка из 16 ячеек

Предположим, вам нужно нарисовать сетку с 16 ячейками и вы можете выбрать для этого 5 разных алгоритмов (из списка выше).

Первый алгоритм займет O(log n) времени. Вы можете осуществлять 10 операций в секунду. Чтобы нарисовать сетку из 16 ячеек, при времени O(log n) вам понадобится осуществить 4 операции (log 16 с основанием 2 это 4). То есть, у вас на это уйдет 0,4с. Что, если нужно нарисовать 1024 ячеек? На это потребуется log 1024 = 10 операций, т. е., 1с. Это первый алгоритм.

Второй алгоритм медленнее, его время выполнения O(n). Чтобы нарисовать 16 ячеек, понадобится 16 операций, а чтобы нарисовать 1024 ячейки — 1024 операции. Сколько это в секундах?

На графиках вы можете увидеть скорость всех алгоритмов, от самого быстрого до самого медленного:

Графики, иллюстрирующие скорость алгоритмов

Есть и другие варианты времени выполнения алгоритмов, но эти встречаются чаще всего.

Конечно, это упрощение. На самом деле вы не сможете так точно конвертировать время, записанное при помощи «О» большого, в количество операций, но это хорошая прикидка.

Заключение

Вот основные вещи, которые нужно усвоить:

  • Скорость алгоритма измеряется не в секундах, а в приросте количества операций.
  • Мы говорим о том, как быстро возрастает время работы алгоритма в зависимости от увеличения объема входящих данных.
  • Время работы алгоритма выражается при помощи нотации большого «О».
  • Алгоритм со скоростью O(log n) быстрее, чем со скоростью O(n), но он становится намного быстрее по мере увеличения списка элементов.

Обозначение O-большое: введение для начинающих разработчиков

Обозначение O-большое – один из самых базовых инструментов информатики для анализа временной и пространственной сложности алгоритма.

Выбор алгоритма и структуры данных начинает иметь значение, когда вам нужно написать программное обеспечение со строгими SLA (соглашениями об уровне обслуживания) или для миллионов пользователей.

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

Что будет рассмотрено в данной статье:

  • Что такое обозначение O-большое?
  • Что такое временная и пространственная сложность?
  • Распространенные разновидности обозначения O-большое
  • Асимптотический анализ: как определить сложность алгоритма
  • Примеры кода для обозначений O-большое
  • Шпаргалка по обозначению O-большое

Что такое обозначение O-большое?

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

Используя обозначение O-большое, вы выражаете, насколько быстро растет время выполнения при росте количества входных данных. По сути, это способ понять, насколько масштабируемым является алгоритм.

Это обозначение не сообщает вам, насколько быстро или медленно будет работать алгоритм, но оно сообщает, как изменяется сложность алгоритма в зависимости от размера входных данных.

Что такое временная и пространственная сложность?

Говоря об обозначении O-большое, важно понимать концепции временной и пространственной сложностей, главным образом потому, что обозначение O-большое – это способ классификации сложностей.

Сложность – это приблизительная мера эффективности алгоритма, связанная с каждым написанным вами алгоритмом. Это то, о чем должны знать все программисты.

Есть два вида сложности: временная и пространственная. Временная сложность и пространственная сложность – это, по сути, аппроксимации того, сколько времени и сколько места потребуется алгоритму для обработки определенных входных данных.

Как правило, необходимо определить три уровня (лучший случай, средний случай и худший случай), которые известны как асимптотические обозначения. Эти обозначения позволяют нам ответить на такие вопросы, как:

  • Не становится ли алгоритм внезапно невероятно медленным при увеличении размера входных данных?
  • Сохраняет ли он быстрое время выполнения при увеличении размера входных данных?

Лучший случай – обозначается как Омега-большое или Ω(n).

Омега-большое (обычно обозначаемая как Ω) представляет собой асимптотическое обозначение для наилучшего случая или минимальную скорость роста для данной функции. Это обозначение дает нам асимптотическую нижнюю границу скорости роста времени выполнения алгоритма.

Средний случай – обозначается как Тета-большое или Θ(n)

Тета (обычно обозначаемая как Θ) является асимптотической записью для обозначения асимптотически жесткой границы скорости роста времени выполнения алгоритма.

Худший случай – обозначается как O-большое или O(n)

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

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

Распространенные разновидности обозначения O-большое

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

O(1) – постоянная временная сложность

O(1) означает постоянное время выполнения, что означает, что независимо от размера входных данных алгоритм будет иметь одинаковое время выполнения.

постоянная временная сложность

Пример:

Массив: вставка или получение элемента

O(log n) – логарифмическая временная сложность

O(log n) означает, что время увеличивается линейно, когда n растет экспоненциально. Таким образом, если для вычисления 10 элементов требуется 1 секунда, то для вычисления 100 элементов потребуется 2 секунды, и так далее. Сложность равна O(log n), когда мы используем алгоритмы «разделяй и властвуй», например, бинарный поиск.

логарифмическая временная сложность

Пример:

Двоичное дерево: вставка или получение элемента

O(n) – линейная временная сложность

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

линейная временная сложность

Пример:

Дерево: поиск в глубину (DFS) дерева

O(n²) – квадратичная временная сложность

По мере увеличения количества элементов в вашем списке время, необходимое для работы вашего алгоритма, будет увеличиваться экспоненциально.

квадратичная временная сложность

Пример:

Алгоритм сортировки: пузырьковая сортировка и сортировка вставками.

Асимптотический анализ: как определить сложность алгоритма

Как найти O-большое алгоритма

Если на собеседовании вас просят определить сложность O-большое алгоритма, вот общее правило:

  • отбросьте ведущие константы;
  • игнорируйте члены более низкого порядка.

Пример: найдите сложность O-большое алгоритма с временной сложностью 3n 3 + 4n + 2.

Это упрощается до O(n 3 ).

Как найти временную сложность алгоритма

При расчете временной сложности алгоритма вам необходимо выполнить три шага:

  1. перечислите все основные операции в коде;
  2. подсчитайте, сколько раз каждая из них была выполнена;
  3. суммируйте все подсчеты, чтобы получить формулу.

Простой пример, который измеряет временную сложность цикла for размером n :

#include using namespace std; int main() < int n = 10; // O(1) int sum = 0; // O(1) for (int i=0; i

Сначала разделите код на отдельные операции, а затем вычислите, сколько раз они выполняются, что будет выглядеть так:

Операция Количество выполнений
int n = 10; 1
int sum = 0; 1
int i = 0; 1
i < n; n + 1
i++; n
sum += 2; n
cout

1

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

Временная сложность = 1+1+1+(n+1)+n+n+1=3+(n+1)+2n+1=>3n+5

Общие советы по асимптотическому анализу:

  • каждый раз, когда список или массив повторяется x раз, сложность, скорее всего, равна O(n);
  • когда вы видите задачу, в которой обрабатываемое количество элементов каждый раз уменьшается вдвое, скорее всего, временная сложность будет равна O(log n);
  • всякий раз, когда у вас есть единожды вложенный цикл, алгоритм, скорее всего, имеет квадратичную временную сложность.

Полезные формулы для расчета временной сложности алгоритма:

Суммирование Формула
\[\left( \sum^n_c \right) = c + c + c + \cdot \cdot \cdot + c\] \[cn\]
\[\left( \sum^n_i \right) = 1 + 2 + 3 + \cdot \cdot \cdot + n\] \[\frac\]
\[\left( \sum^n_i^2 \right) = 1 + 4 + 9 + \cdot \cdot \cdot + n^2\] \[\frac\]
\[\left( \sum^n_r^i \right) = r^0 + r^1 + r^2 + \cdot \cdot \cdot + r^n\] \[\frac-1>\]

Примеры кода для обозначений O-большое

О(1)

 void printFirstItem(const vector& items)

Данная функция выполняется за время O(1) (или «постоянное время») относительно своих входных данных. Это означает, что входной массив может состоять из 1 или 1000 элементов, но для данной функции всё равно потребуется всего один «шаг».

О(n)

void printAllItems(const vector& items) < for (int item : items) < cout >

Данная функция выполняется за время O(n) (или «линейное время»), где n – количество элементов в векторе. Если в векторе 10 элементов, необходимо 10 операций печати. Если в нем 1000 элементов, нам придется выполнить 1000 операций печати.

O(n 2 )

void printAllPossibleOrderedPairs(const vector& items) < for (int firstItem : items) < for (int secondItem : items) < cout > >

Здесь у нас два вложенных цикла. Если наш вектор содержит n элементов, наш внешний цикл выполняется n раз, а наш внутренний цикл запускается n раз для каждой итерации внешнего цикла, давая нам общее количество операций печати n 2 . Таким образом, данная функция выполняется за время O(n 2 ) (или «квадратичное время»). Если в векторе 10 элементов, нам нужно выполнить 100 операций печати. Если в нем 1000 элементов, нам придется выполнить 1000000 операций печати.

Шпаргалка по обозначению O-большое

Структура данных Худший случай Примечания
Массив Вставка: O(1)
Получение элемента: O(1)
Связный список Вставка в конец: O(n)
Вставка в начало: O(1)
Получение элемента: O(n)
Обратите внимание, что, если новые элементы добавляются в начало связанного списка, сложность операции вставки становится O(1)
Двоичное дерево Вставка в конец: O(n)
Получение элемента: O(n)
В худшем случае двоичное дерево становится связанным списком.
Динамический массив Вставка: O(1)
Получение элемента: O(1)
Обратите внимание, что при извлечении подразумевается, что мы извлекаем элемент с определенным индексом массива.
Стек Добавление элемента (push): O(1)
Удаление элемента (pop): O(1)
Очередь Добавление в очередь: O(1)
Удаление из очереди: O(1)
Приоритетная очередь (двоичная куча) Вставка: O(log n)
Удаление: O(log n)
Получение min/max: O(1)
Хеш-таблица Вставка: O(n)
Получение: O(n)
Помните, что средний случай вставки и извлечения из хеш-таблицы – O(1)
B-деревья Вставка: O(log n)
Получение: O(log n)
Красно-черные деревья Вставка: O(log n)
Получение: O(log n)
Алгоритм Худший случай Примечания
Алгоритмы сортировки/поиска Пузырьковая сортировка: O(n 2 )
Сортировка вставками: O(n 2 )
Сортировка выбором: O(n 2 )
Быстрая сортировка: O(n 2 )
Сортировка слиянием: O(log n)
Обратите внимание, хотя производительность быстрой сортировки в худшем случае составляет O(n 2 ), но на практике она используется часто, поскольку ее средний случай - O(n log n).
Алгоритмы работы с деревьями Поиск в глубину: O(n)
Поиск в ширину: O(n)
Прямой, центрированный и обратный обходы: O(n)
n – общее количество узлов в дереве. Большинство алгоритмов обхода дерева в конечном итоге просматривает каждый узел в дереве, и их сложность в худшем случае, таким образом, составляет O(n).

Теги

Сохранить или поделиться

На сайте работает сервис комментирования DISQUS, который позволяет вам оставлять комментарии на множестве сайтов, имея лишь один аккаунт на Disqus.com.

В случае комментирования в качестве гостя (без регистрации на disqus.com) для публикации комментария требуется время на премодерацию.

О-большое

«O» большое и «o» малое (\mathcal<O> и \mathrm<o>\!\,) — математические обозначения для сравнения асимптотического поведения функций. Используются в различных разделах математики, но активнее всего — в математическом анализе, теории чисел и комбинаторике, а также при оценке сложности алгоритмов. В частности, фраза «сложность алгоритма есть O(n!)» означает, что при больших n время работы алгоритма (или общее количество операций) не более чем C · n!, где C — некая положительная константа (обычно в качестве параметра n берут объём входной информации алгоритма).

Определения

Пусть f(x) и g(x) — две функции, определенные в некоторой проколотой окрестности точки x0 , причем в этой окрестности g не обращается в ноль. Говорят, что:

  • f является «O» большим от g при x\to x_0, если существует константа C > 0 , что для всех x из некоторой окрестности точки x0 имеет место неравенство |f(x)| \leqslant C |g(x)|;
  • f является «о» малым от g при x\to x_0, если для любого \varepsilon&gt;0найдется такая проколотая окрестность U_<x_0> точки x0 , что для всех x\in U_<x_0> имеет место неравенство |f(x)| \leqslant \varepsilon |g(x)|.

x\to x_0

Иначе говоря, в первом случае отношение | f | / | g | в окрестности точки x0 ограничено сверху, а во втором оно стремится к нулю при .

Обозначение

Обычно выражение «f является „O“ большим („о“ малым) от g» записывается с помощью равенства f(x) = O(g(x)) (соответственно, f(x) = o(g(x))).

Это обозначение очень удобно, но требует некоторой осторожности при использовании (а потому в наиболее элементарных учебниках его могут избегать). Дело в том, что это не равенство в обычном смысле, а несимметричное отношение.

В частности, можно писать

f(x) = O(g(x)) (или f(x) = o(g(x))),

O(g(x)) = f(x) (или o(g(x)) = f(x))

Другой пример: при x → 0 верно, что

O(x²) = o(x),

o(x) = O(x²).

Вместо знака равенства методологически правильнее было бы употреблять знаки принадлежности и включения, понимая O( ) и o( ) как обозначения для множеств функций, то есть используя запись в форме

x² + x³ ∈ O(x²)

\mathop O(x^2)\subset o(x)

x² + x³ = O(x²)

\mathop O(x^2) = o(x)

Однако на практике такая запись встречается крайне редко, в основном в простейших случаях.

При использовании данных обозначений должно быть явно оговорено (или очевидно из контекста), о каких окрестностях (одно- или двусторонних; содержащих целые, вещественные или комплексные числа и т. п.) и о каких допустимых множествах функций идет речь (поскольку такие же обозначения употребляются и применительно к функциям многих переменных, к функциям комплексной переменной, к матрицам и др.).

Другие подобные обозначения

Для функций f(n) и g(n) при n → n0 используются следующие обозначения:

Обозначение Интуитивное объяснение Определение
f(n) \in O(g(n)) f ограничена сверху функцией g (с точностью до постоянного множителя) асимптотически \exists (C&gt;0), U : \forall (n \in U) \; |f(n)| \leq C|g(n)|
f(n) \in \Omega(g(n)) f ограничена снизу функцией g (с точностью до постоянного множителя) асимптотически \exists (C&gt;0), U : \forall (n \in U) \; C|g(n)| \leq |f(n)|
f(n) \in \Theta(g(n)) f ограничена снизу и сверху функцией g асимптотически \exists (C&gt;0), (C
f(n) \in o(g(n)) g доминирует над f асимптотически \forall (C&gt;0) ,\exists U : \forall(n \in U) \; |f(n)| &lt; C|g(n)|
f(n) \in \omega(g(n)) f доминирует над g асимптотически \forall (C&gt;0) ,\exists U : \forall(n \in U) \; C|g(n)| &lt; |f(n)|
f(n) \sim g(n)\! f эквивалентна g асимптотически \lim_<n \to n_0>\frac = 1

где U — проколотая окрестность точки n0.

Основные свойства

Транзитивность

\begin</p> <ul> <li>f(n)=\Theta(g(n)) \land g(n)=\Theta(h(n)) &amp; \Rightarrow &amp; f(n) = \Theta (h(n)) \\ f(n)=O(g(n)) \land g(n)=O (h(n)) &amp; \Rightarrow &amp; f(n) = O (h(n)) \\ f(n)=\Omega(g(n)) \land g(n)=\Omega(h(n)) &amp; \Rightarrow &amp; f(n) = \Omega(h(n)) \\ f(n)=o(g(n)) \land g(n)= o (h(n)) &amp; \Rightarrow &amp; f(n) = o (h(n)) \\ f(n)=\omega(g(n)) \land g(n)=\omega(h(n)) &amp; \Rightarrow &amp; f(n) = \omega(h(n))\end

Рефлексивность

  • f(n)=\Theta(f(n))\!
  • f(n)=O(f(n))\!
  • f(n)=\Omega(f(n))\!

Симметричность

  •  f(n)=\Theta(g(n)) \Leftrightarrow g(n)=\Theta(f(n))

Перестановочная симметрия

 \begin</p> <p> f(n)= O(g(n)) &amp; \Leftrightarrow &amp; g(n)=\Omega(f(n)) \\ f(n)= o(g(n)) &amp; \Leftrightarrow &amp; g(n)=\omega(f(n)) \end

Другие

Асимптотические обозначения в уравнениях

\sum_<i=0></p> <ul> <li>Если в правой части уравнения находится только асимптотическое обозначение (например <i>n</i> = <i>O</i>(<i>n</i>²)), то знак равенства обозначает принадлежность множеству (<i>n</i> ∈ <i>O</i>(<i>n</i>²)).</li> <li>Если в уравнении асимптотические обозначения встречается в другой ситуации, они рассматриваются как подставляемые взамен их некоторые функции. Например, при <i>x</i> → 0 формула <i>e</i><i>x</i> − 1 = <i>x</i> + <i>o</i>(<i>x</i>) обозначает, что <i>e</i><i>x</i> − 1 = <i>x</i> + <i>f</i>(<i>x</i>) , где <i>f</i>(<i>x</i>) — функция, о которой известно только то, что она принадлежит множеству <i>o</i>(<i>x</i>) . Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения. Например, ^nO(n_i^2) — содержит только одну функцию из класса O(n 2 ) .

  • Если асимптотические обозначения встречаются в левой части уравнения, используют следующее правило:
    какие бы мы функции не выбрали (в соответствии с предыдущим правилом) взамен асимптотических обозначений в левой части уравнения, можно выбрать функции вместо асимптотических обозначений (в соответствии с предыдущим правилом) в правой части так, что уравнение будет правильным.
    Например, запись x + o(x) = O(x) обозначает, что для любой функции f(x) ∈ o(x) , существует некоторая функция g(x) , такая что выражение x + f(x) = g(x) — верно для всех x .
  • Несколько таких уравнений могут быть объединены в цепочки. Каждое из уравнений в таком случае следует интерпретировать в соответствии с прдыдущим правилом.
    Например: 4n 4 + 4n 2 + 1 = 4n 4 + Θ(n 2 ) = Θ(n 4 ) . Отметим, что такая интерпретация подразумевает выполнение соотношения 4n 4 + 4n 2 + 1 = Θ(n 4 ) .
  • Приведенная интерпретация подразумевает выполнение соотношения:

    \left. \begin</p> <p>A = B \\ B = C \end \right\> \Rightarrow A = C, где A, B, C — выражения, которые могут содержать асимптотические обозначения.

    Примеры использования

    • e x = 1 + x + x²/2 + O(x³) при x → 0.
    • n! = O((n/e) n+1/2 ) при n → ∞.
    • T(n) = (n + 1) 2 = O(n 2 ) при n → ∞.
    • Функция T(n) = 3n 3 + 2n 2 при n → ∞ имеет степень роста O(n 3 ) . Чтобы это показать, надо положить n0 = 0 и c = 5 . Можно, конечно, сказать, что T(n) имеет порядок O(n 4 ) , но это более слабое утверждение, чем то, что T(n) имеет порядок роста O(n 3 ) .
    • Докажем, что функция 3 n при n → ∞ не может иметь порядок O(2 n ) . Предположим, что существуют константы c и n0 такие, что для всех nn0 выполняется неравенство 3 nc2 n . Тогда c ≥ (3/2) n для всех nn0. Но (3/2) n принимает любое, как угодно большое, значение при достаточно большом n , поэтому не существует такой константы c , которая могла бы мажорировать (3/2) n для всех n больших некоторого n0.
    • T(n) = n 3 + 2n 2 есть Ω(n 3 ) при n → ∞. Для проверки достаточно положить c = 1 . Тогда T(n) >cn 3 для n = 0,1. .

    История

    Обозначение «„O“ большое» введено немецким математиком Паулем Бахманом (Paul Gustav Heinrich Bachmann) во втором томе его книги «Analytische Zahlentheorie» (Аналитическая теория чисел), вышедшем в 1894 году. Обозначение «„о“ малое» впервые использовано другим немецким математиком, Эдмундом Ландау (Edmund Georg Hermann Landau) в 1909 году; с работами последнего связана и популяризация обоих обозначений, в связи с чем их также называют символами Ландау.

    См. также

    Литература

    • Д. Грин, Д. Кнут. Математические методы анализа алгоритмов : Пер. с англ. М.: Мир, 1987. — 120 с.
    • Дж. Макконелл, Основы современных алгоритмов, Изд. 2 доп., М.: «Техносфера», 2004, 368 с ISBN 5-94836-005-9
    • Джон Э. Сэвидж, Сложность вычислений, М.: «Факториал», 1998, 368 с ISBN 5-88688-039-9
    • В. Н. Крупский, Введение в сложность вычислений, М.: «Факториал Пресс», 2006, 128 с ISBN 5-88688-083-6
    • Herbert S. Wilf, Algorithms and Complexity, http://www.math.upenn.edu/~wilf/AlgComp3.html
    • Кормен, Томас Х.; Лейзерсон, Чарльз И.; Ривест, Рональд Л.; Штайн, КлифордГлава 3. Рост функций // Алгоритмы: построение и анализ, 2-е издание = Introduction to Algorithms second edition. — М.: «Вильямс», 2005. — С. 230 - 234. — ISBN 5-8459-0857-4

    Wikimedia Foundation . 2010 .

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *