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

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

Я пропустил этот университетский class, я думаю: 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 , она рано или поздно обгонит ее – это точно).

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

    Например (в 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; } 

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

    Это означает, что вы будете копировать первую букву 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, а setCapacity с setCapacity бы 1000 операций, чтобы сделать то же самое. Это приблизительная оценка, но O(n) обозначение - порядка порядков величин, а не точное время выполнения.

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

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

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

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

    2) Такие действия, как ‘add’ / ‘sort’ / ‘remove’, могут занимать разные промежутки времени с разными структурами данных (и алгоритмами), например ‘add’ и ‘find’ являются O (1) для hashmap, но 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> 100 вы увидите, что f (x)> g (x), то f (x) «быстрее», чем g (x).

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

    Это не совсем точное определение нотации O-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?

    Нотация Big O – это способ выражения отношения между многими шагами, которые потребует алгоритм, связанный с размером входных данных. Это называется алгоритмической сложностью. Например, сортировка списка размера N с использованием Bubble Sort выполняет шаги 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 итераций. В нотации Big O это O (n).

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

    Interesting Posts

    Почему Windows 7 устанавливает 64-разрядные приложения в папку Program Files (x86)? Могу ли я изменить поведение?

    Точность и точность System.nanoTime ()

    Как мне заставить IE8 открывать пустую страницу с помощью CTRL-N?

    Изменить цвет фона одной ячейки в JTable

    Преимущества, проблемы, примеры добавления другого UIWindow в приложение iOS?

    Как я могу вызвать конкретный метод Java при нажатии / отправке события определенной кнопки в JSP?

    Selenium WebDriver : как нажимать на элементы в SVG с помощью XPath

    Алгоритм для поиска следующей большей перестановки заданной строки

    Включить заголовки при использовании SELECT INTO OUTFILE?

    javax.net.ssl.SSLException: Получено фатальное предупреждение: protocol_version

    Имеет ли float отрицательный ноль? (-0f)

    Размер шрифта Bind в JavaFX?

    Преобразование столбца в pandas dataframe из int в строку

    # 1130 – Host ‘localhost’ не разрешено подключаться к этому серверу MySQL

    Спасение возможно поврежденного PDF в Acrobat

    Давайте будем гением компьютера.