Что такое обозначение Big O?Вы его используете?[дубликат]

https://stackoverflow.com/questions/133008

02-07-2019
|

Вопрос

На этот вопрос уже есть ответ здесь:

Каково простое английское объяснение обозначения «Большое О»? 39 ответов

Что такое обозначение Big O?Вы его используете?

Наверное, я пропустил этот университетский урок :D

Кто-нибудь использует его и приводит примеры из реальной жизни, где он его использовал?

Решение

Говоря о Big-O, большинство людей забывают одну важную вещь, поэтому я чувствую необходимость упомянуть следующее:

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

Однако если у вас есть два совершенно разных алгоритма и один (A) является O(n^2) и еще один(B) является O(log n), не сказано, что A медленнее, чем B.На самом деле, со 100 предметами, A может быть в десять раз быстрее, чем B.Там написано только, что при 200 элементах A будет расти медленнее в разы n^2 и B будет расти медленнее в разы log n.Итак, если вы сравните оба показателя и знаете, сколько времени A требуется для обработки 100 позиций и сколько времени B потребности в тех же 100 предметах, и A быстрее, чем B, вы можете посчитать, на какое количество предметов B обгонит A по скорости (как скорость B убывает гораздо медленнее, чем A, оно обгонит A рано или поздно — это точно).

Другие советы

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

Например (на Java):

/** Takes an array of strings and concatenates them
  * This is a silly way of doing things but it gets the 
  * point across hopefully
  * @param strings the array of strings to concatenate
  * @returns a string that is a result of the concatenation of all the strings
  *          in the array
  */
public static String badConcat(String[] Strings){
    String totalString = "";
    for(String s : strings) {
        for(int i = 0; i < s.length(); i++){
            totalString += s.charAt(i);
        }
    }
    return totalString;
}

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

Это означает, что вы будете копировать первую букву н времена, когда н — количество символов во входных данных.Вы будете копировать персонажа n-1 раз, так что всего будет (n-1)(n/2) копии.

Это (n^2-n)/2 а для обозначения Big O мы используем только самый высокий коэффициент величины (обычно) и отбрасываем все константы, которые умножаются на него, и в итоге мы получаем O(n^2).

Используя что-то вроде StringBuilder будет соответствовать O(nLog(n)).Если вы подсчитаете количество символов вначале и зададите емкость StringBuilder ты можешь заставить это быть O(n).

Итак, если бы у нас было 1000 входных символов, первый пример выполнил бы примерно миллион операций. StringBuilder выполнит 10 000, а StringBuilder с setCapacity выполнил бы 1000 операций, чтобы сделать то же самое.Это приблизительная оценка, но O(n) обозначение относится к порядкам величин, а не к точному времени выполнения.

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

Очень похожий вопрос уже задавался Big-O для восьмилетних?.Надеюсь, ответы там ответят на ваш вопрос, хотя задавший вопрос имел некоторые математические знания обо всем этом, которых у вас может не быть, поэтому уточните, если вам нужно более полное объяснение.

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

1) Это порядок измерения эффективности алгоритма при работе со структурой данных.

2) Такие действия, как «добавить» / «сортировать» / «удалить», могут занимать разное количество времени с разными структурами данных (и алгоритмами), например «добавить» и «найти» - это O (1) для хэш-карты, но O (log n) для двоичного дерева.Сортировка — это O(nlog n) для быстрой сортировки, но O(n^2) для BubbleSort при работе с простым массивом.

3) Расчеты можно выполнить, посмотрев на глубину цикла вашего алгоритма в целом.Никаких циклов, O(1), циклов, повторяющихся по всему множеству (даже если в какой-то момент они вырываются) O(n).Если цикл уменьшает вдвое пространство поиска на каждой итерации?О(логарифм n).Возьмите наибольшее значение O() для последовательности циклов и умножьте значение O() при вложении циклов.

Да, это сложнее.Если вам действительно интересно, возьмите учебник.

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

Оказывается, это очень полезная идея в информатике и особенно при анализе алгоритмов, поскольку нас часто интересует именно скорость роста функций, которые представляют, например, время, затрачиваемое двумя разными алгоритмами.Грубо говоря, мы можем определить, что алгоритм со временем выполнения t1(n) более эффективен, чем алгоритм со временем выполнения t2(n), если t1 = O(t2) для достаточно большого n, которое обычно является «размером» проблема - например, длина массива или количество узлов в графе или что-то еще.

Это условие, что n становится достаточно большим, позволяет нам использовать множество полезных трюков.Возможно, наиболее часто используемым является то, что вы можете упростить функции до их наиболее быстро развивающихся терминов.Например, n^2 + n = O(n^2), потому что, когда n становится достаточно большим, член n^2 становится намного больше чем n, то член n практически незначителен.Поэтому мы можем исключить это из рассмотрения.

Однако это означает, что нотация big-O менее полезна для маленьких n, поскольку члены с более медленным ростом, о которых мы забыли, все еще достаточно значительны, чтобы повлиять на время выполнения.

Теперь у нас есть инструмент для сравнения затрат двух разных алгоритмов и сокращение для того, чтобы сказать, что один быстрее или медленнее другого.Обозначением Big-O можно злоупотреблять, и это досадно, поскольку оно и так достаточно неточно!Существуют эквивалентные термины, обозначающие, что одна функция растет медленнее, чем другая, и что две функции растут с одинаковой скоростью.

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

«Интуиция» позади Big-O

Представьте себе «конкуренцию» между двумя функциями по x, когда x приближается к бесконечности:f(x) и g(x).

Теперь, если с некоторого момента (некоторого x) одна функция всегда имеет более высокое значение, чем другая, то давайте назовем эту функцию «быстрее», чем другую.

Так, например, если для каждого x > 100 вы видите, что f(x) > g(x), то f(x) «быстрее», чем g(x).

В этом случае мы бы сказали g(x) = O(f(x)).f(x) представляет собой своего рода «ограничение скорости» для g(x), поскольку в конечном итоге она его преодолевает и навсегда оставляет позади.

Это не совсем определение обозначение «большое О», который также утверждает, что f(x) должно быть больше, чем C*g(x) только для некоторой константы C (это просто еще один способ сказать, что вы не можете помочь g(x) выиграть соревнование, умножив его на постоянный коэффициент - f(x) в конечном итоге всегда выиграет).В формальном определении также используются абсолютные значения.Но я надеюсь, что мне удалось сделать это интуитивно понятным.

Возможно, также стоит учитывать, что сложность многих алгоритмов основана на более чем одной переменной, особенно в многомерных задачах.Например, недавно мне пришлось написать алгоритм для следующего.Учитывая набор из n точек и m многоугольников, извлеките все точки, лежащие в любом из многоугольников.Сложность основана на двух известных переменных, n и m, и неизвестном количестве точек в каждом многоугольнике.Обозначение большого O здесь немного сложнее, чем O(f(n)) или даже O(f(n) + g(m)).Большой О хорош, когда вы имеете дело с большим количеством однородных элементов, но не ждите, что так будет всегда.

Также стоит отметить, что фактическое количество итераций над данными часто зависит от самих данных.Быстрая сортировка обычно выполняется быстро, но если предоставить ей предварительно отсортированные данные, она замедлится.Мой алгоритм точек и полигонов оказался довольно быстрым, близким к O(n + (m log(m)), основываясь на предварительном знании того, как данные могут быть организованы, и относительных размерах n и m.Это плохо сработает на случайно организованных данных разных относительных размеров.

И последнее, что следует учитывать: часто существует прямой компромисс между скоростью алгоритма и объемом используемого им пространства. Сортировка по голубятням это довольно хороший пример этого.Возвращаясь к моим точкам и полигонам, скажем, что все мои полигоны рисовались просто и быстро, и я мог рисовать их заполненными на экране, скажем синим цветом, за фиксированное время каждый.Итак, если я нарисую m полигонов на черном экране, это займет время O(m).Чтобы проверить, находится ли какая-либо из моих n точек в многоугольнике, я просто проверяю, является ли пиксель в этой точке зеленым или черным.Таким образом, проверка составляет O(n), а общий анализ — O(m + n).Обратной стороной, конечно, является то, что мне нужно почти бесконечное хранилище, если я имею дело с координатами реального мира с точностью до миллиметра....... хо хм.

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

Хорошим примером является динамическая таблица, которая по сути представляет собой массив, который расширяется по мере добавления в него элементов.Наивная реализация увеличила бы размер массива на 1 для каждого добавленного элемента, а это означает, что все элементы необходимо копировать каждый раз, когда добавляется новый.Это приведет к На²) алгоритм, если вы объединяли серию массивов с помощью этого метода.Альтернативой является удвоение емкости массива каждый раз, когда вам нужно больше места для хранения.Несмотря на то, что добавление является На) иногда вам нужно будет только скопировать На) элементы для каждого н добавлены элементы, поэтому операция О(1) в среднем.Вот такие дела Строитель строк или станд::вектор реализованы.

Что такое обозначение Big O?

Обозначение Big O — это метод выражения взаимосвязи между многими шагами, которые потребуются алгоритму, в зависимости от размера входных данных.Это называется алгоритмической сложностью.Например, сортировка списка размера N с помощью пузырьковой сортировки занимает O(N^2) шагов.

Использую ли я обозначение Big O?

Иногда я использую нотацию Big O, чтобы донести до коллег-программистов сложность алгоритма.Я использую основную теорию (например.Методы анализа Big O) все время, когда я думаю о том, какие алгоритмы использовать.

Конкретные примеры?

Я использовал теорию анализа сложности для создания алгоритмов для эффективных структур данных стека, которые не требуют перераспределения памяти и поддерживают среднее время O(N) для индексации.Я использовал обозначение Big O, чтобы объяснить алгоритм другим людям.Я также использовал анализ сложности, чтобы понять, когда возможна сортировка по линейному времени O(N).

Из Википедии.....

Обозначение Big O полезно при анализе эффективности алгоритмов.Например, время (или количество шагов), необходимое для решения задачи размера n, можно определить как T(n) = 4n² − 2n + 2.

По мере того, как n становится большим, член n² станет доминировать, так что всеми остальными членами можно будет пренебречь - например, когда n = 500, член 4n² в 1000 раз больше, чем член 2n.Игнорирование последнего оказало бы незначительное влияние на значение выражения для большинства целей.

Очевидно, я никогда не использовал его..

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

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

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

Допустим, в списке n элементов.В худшем случае вам потребуется n итераций.В обозначении Большого О это O(n).

Фактически это говорит о том, насколько эффективен алгоритм.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow

Что такое обозначение Big O?Вы его используете?[дубликат]

Смотрите также:

Что такое обозначение Big O?

Использую ли я обозначение Big O?

Конкретные примеры?