Что такое примечание Big O? Вы используете его?
Я пропустил этот университетский класс, я думаю: D
Кто-нибудь использует его и дает некоторые реальные примеры того, где они его использовали?
Big-O для восьмилетних детей?
Big O, как вы его вычисляете/приближаете?
Вы применили теорию сложности вычислений в реальной жизни?
Одна важная вещь, которую большинство людей забывает, когда говорит о 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 раз, где n - количество символов на входе. Вы будете копировать символ 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) Действия, подобные 'add'/'sort'/'remove', могут занимать разные промежутки времени с разными структурами данных (и алгоритмами), например, 'add' и 'find' являются O (1) для хэш-карты, но O (log n) для двоичного дерева. Сортировка - O (nlog n) для QuickSort, но O (n ^ 2) для BubbleSort при работе с простым массивом.
3) Расчеты можно выполнить, просмотрев глубину петли вашего алгоритма в целом. Нет циклов, O (1), петли повторяются по всему набору (даже если они разрываются в какой-то момент) O (n). Если петля уменьшает пространство поиска на каждой итерации? O (log 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), так как в конце концов он передает его и оставляет его навсегда.
Это не совсем точное определение примечание Big-O, в котором также указано, что f (x) должно быть больше, чем C * g (x) для некоторой константы C (что является еще одним способом сказать, что вы не можете помочь g (x) выиграть соревнование, умножив его на постоянный коэффициент - f (x) всегда победит в конце), Формальное определение также использует абсолютные значения. Но я надеюсь, что мне удалось сделать его интуитивным.
Можно также счесть, что сложность многих алгоритмов основана на нескольких переменных, особенно в многомерных задачах. Например, недавно мне пришлось написать алгоритм для следующего. Учитывая множество n точек и m полигонов, извлеките все точки, которые лежат в любом из многоугольников. Сложность основана на двух известных переменных: n и m и неизвестном количестве точек в каждом полигоне. Большая нотация O здесь немного больше, чем O (f (n)) или даже O (f (n) + g (m)). Big O хорош, когда вы имеете дело с большим количеством однородных предметов, но не ожидайте, что это всегда будет иметь место.
Также стоит отметить, что фактическое количество итераций по данным часто зависит от данных. Quicksort, как правило, быстрый, но дает предварительные данные, и он замедляется. Мои точки и полигоны alogorithm оказались довольно быстрыми, близкими к O (n + (m log (m)), основываясь на предварительном знании того, как данные могут быть организованы, и относительных размеров n и m. плохо на случайно организованных данных разных относительных размеров.
Последнее, что нужно учитывать, заключается в том, что часто существует прямая компромисс между скоростью алгоритма и объемом используемого им пространства. Сортировка отверстий для голубей - довольно хороший пример этого. Возвращаясь к моим точкам и полигонам, скажем, что все мои полигоны были простыми и быстрыми, и я мог рисовать их на экране, синим цветом, в фиксированном количестве времени каждый. Поэтому, если я нарисую свои m-полигоны на черном экране, потребуется время O (m). Чтобы проверить, была ли какая-либо из моих n точек в полигоне, я просто проверяю, является ли пиксель в этой точке зеленым или черным. Таким образом, проверка O (n), а общий анализ - O (m + n). Конечно, недостатком является то, что мне нужно около бесконечного хранилища, если я имею дело с реальными мировыми координатами с точностью до миллиметра....... ho hum.
Возможно, стоит подумать и о амортизированном времени, а не о худшем случае. Это означает, например, что если вы будете запускать алгоритм n раз, это будет O (1) в среднем, но иногда это может быть хуже.
Хорошим примером является динамическая таблица, которая в основном представляет собой массив, который расширяется по мере добавления к нему элементов. Наивная реализация увеличит размер массива на 1 для каждого добавленного элемента, а это означает, что все элементы нужно копировать каждый раз, когда добавляется новый. Это приведет к алгоритму O (n 2), если вы объединили ряд массивов с использованием этого метода. Альтернативой является удвоение емкости массива каждый раз, когда вам нужно больше места для хранения. Несмотря на то, что добавление иногда является операцией O (n), вам нужно будет только скопировать элементы O (n) для каждого n добавленных элементов, поэтому операция будет равна O (1) в среднем. Вот как реализованы такие вещи, как StringBuilder или std::vector.
Обозначение Big O - это способ выражения отношения между многими шагами, которые потребует алгоритм, связанный с размером входных данных. Это называется алгоритмической сложностью. Например, сортировка списка размера N с использованием Bubble Sort выполняет шаги O (N ^ 2).
Я использую нотацию 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 итераций. В нотации Big O это O (n).
В нем говорится, насколько эффективен алгоритм.