39 Вопрос: Что такое простое английское объяснение обозначения «Big O»?

вопрос создан в Fri, Jul 22, 2016 12:00 AM

Я бы предпочел как можно меньше формального определения и простую математику.

    
4766
  1. Резюме: верхняя граница сложности алгоритма. Смотрите также похожий вопрос Big O, как вы рассчитываете /приближаете его? для хорошего объяснения.
    2009-01-28 11: 18: 44Z
  2. Другие ответы довольно хороши, только одна деталь, чтобы понять это: O (log n) или подобное означает, что это зависит от "длины" или "размера" ввода, а не на само значение. Это может быть трудно понять, но это очень важно. Например, это происходит, когда ваш алгоритм делит вещи на две части в каждой итерации.
    2009-01-28 11: 23: 43Z
  3. В лекции 8 курса MIT "Введение в информатику и программирование" есть лекция, посвященная сложности алгоритмов youtube.com/watch?v=ewd7Lf2dr5Q Это не совсем простой английский, но дает хорошее объяснение с примерами, которые легко понять.
    2010-07-17 20: 57: 40Z
  4. Большой O - это оценка производительности функции в худшем случае при условии, что алгоритм выполнит максимальное количество итераций.
    2012-08-28 00: 16: 57Z
  5. 2013-09-07 18: 02: 25Z
30 ответов                              30                         

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

Большая сложность O может быть визуализирована с помощью этого графика:

Анализ Big O

Самое простое определение, которое я могу дать для обозначения Big-O, это:

Нотация Big-O является относительным представлением сложности алгоритма.

В этом предложении есть несколько важных и намеренно выбранных слов:

  
  • родственник: вы можете сравнивать только яблоки с яблоками. Вы не можете сравнить алгоритм для выполнения арифметического умножения с алгоритмом, который сортирует список целых чисел. Но сравнение двух алгоритмов для выполнения арифметических операций (одно умножение, одно сложение) скажет вам что-то значимое;
  •   
  • представление: Big-O (в простейшем виде) сводит сравнение между алгоритмами к одной переменной. Эта переменная выбирается на основе наблюдений или предположений. Например, алгоритмы сортировки обычно сравниваются на основе операций сравнения (сравнение двух узлов для определения их относительного порядка). Это предполагает, что сравнение стоит дорого. Но что, если сравнение дешево, а обмен дорог? Это меняет сравнение; и
  •   
  • сложность: если мне понадобится одна секунда, чтобы отсортировать 10000 элементов, сколько времени потребуется, чтобы отсортировать миллион? Сложность в этом случае является относительной мерой к чему-то другому.
  •   

Вернитесь и перечитайте вышесказанное, когда прочтете все остальное.

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

  
    добавление;    вычитание;   
  • мультипликация; и
  •   
  • деление.
  •   

Каждый из них является операцией или проблемой. Метод решения этих проблем называется алгоритм .

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

Давайте предположим, что добавление этих чисел является самой дорогой операцией в этом алгоритме. Само собой разумеется, что для сложения этих двух чисел мы должны сложить вместе 6 цифр (и, возможно, 7). Если мы добавим два 100-значных числа вместе, мы должны сделать 100 добавлений. Если мы добавим два 10000-значных чисел, нам потребуется 10 000 добавлений.

Видите образец? сложность (количество операций) прямо пропорциональна количеству цифр n в большем числе. Мы называем это O (n) или линейной сложностью .

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

Умножение отличается. Вы выстраиваете числа вверх, берете первую цифру в нижнем числе и умножаете ее по очереди на каждую цифру в верхнем числе и так далее до каждой цифры. Таким образом, чтобы умножить наши два 6-значных чисел, мы должны сделать 36 умножений. Возможно, нам понадобится добавить 10 или 11 столбцов, чтобы получить конечный результат.

Если у нас есть два 100-значных числа, нам нужно сделать 10 000 умножений и 200 сложений. Для двух миллионов чисел нам нужно сделать триллион (10 12 ) умножений и два миллиона сложений.

Поскольку алгоритм масштабируется с n- в квадрате , это O (n 2 ) или квадратичная сложность , Самое время представить еще одну важную концепцию:

Мы заботимся только о самой значительной части сложности.

Проницательный, возможно, понял, что мы можем выразить число операций как: n 2 + 2n. Но, как вы видели из нашего примера с двумя числами в миллион цифр за штуку, второй член (2n) становится незначительным (составляя 0,0002% от общего числа операций на этом этапе).

Можно заметить, что мы предположили худший вариант развития событий здесь. При умножении 6-значных чисел, если одно из них является 4-значным, а другое - 6-значным, мы имеем только 24 умножения. Тем не менее мы рассчитываем сценарий наихудшего случая для этого 'n', т.е. когда оба являются 6-значными числами. Следовательно, запись Big-O относится к наихудшему сценарию алгоритма.

Телефонная книга

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

Теперь, если бы вы указали компьютеру найти номер телефона «Джона Смита» в телефонной книге, содержащей 1000000 имен, что бы вы сделали? Игнорируя тот факт, что вы можете догадаться, как далеко в S началось (предположим, вы не можете), что бы вы сделали?

Типичная реализация может состоять в том, чтобы открыть до середины, взять 500 000 -го и сравнить его со «Смитом». Если это «Смит, Джон», нам просто повезло. Гораздо более вероятно, что «Джон Смит» будет до или после этого имени. Если это после того, как мы разделим вторую половину телефонной книги пополам и повторите. Если это раньше, то мы разделяем первую половину телефонной книги пополам и повторяем. И так далее.

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

Итак, если вы хотите найти имя в телефонной книге из миллиона имен, вы можете найти любое имя, выполнив это не более 20 раз. Сравнивая алгоритмы поиска, мы решаем, что это сравнение - наше 'n'.

  
  • Для телефонной книги из 3 имен требуется 2 сравнения (не более).
  •   
  • Для 7 требуется максимум 3.
  •   
  • Для 15 требуется 4.
  •   
  • ...
  •   
  • Для 1 000 000 требуется 20.
  •   

Это потрясающе хорошо, не так ли?

В терминах Big-O это O (log n) или логарифмическая сложность . Теперь рассматриваемый логарифм может быть ln (база e), log 10 , log 2 или какая-либо другая база. Неважно, что это все еще O (log n), точно так же, как O (2n 2 ) и O (100n 2 ) все еще оба O (n 2 ). р>

На этом этапе стоит объяснить, что Big O можно использовать для определения трех случаев с помощью алгоритма:

  
  • Лучший случай . При поиске в телефонной книге лучший случайна мы находим имя в одном сравнении. Это O (1) или постоянная сложность ;
  •   
  • Ожидаемый случай . Как обсуждалось выше, это O (log n); и
  •   
  • В худшем случае . Это также O (log n).
  •   

Обычно мы не заботимся о лучшем случае. Нас интересует ожидаемый и наихудший случай. Иногда одно или другое из них будет более важным.

Вернуться к телефонной книге.

Что если у вас есть номер телефона и вы хотите найти имя? У полиции есть обратная телефонная книга, но такие просмотры запрещены для широкой публики. Или они? Технически вы можете изменить поиск номера в обычной телефонной книге. Как?

Вы начинаете с имени и сравниваете число. Если это совпадение, отлично, если нет, переходите к следующему. Вы должны сделать это так, потому что телефонная книга неупорядочена (по номеру телефона в любом случае).

Итак, чтобы найти имя по номеру телефона (обратный поиск):

  
  • Лучший случай : O (1);
  •   
  • Ожидаемый случай: O (n) (для 500 000); и
  •   
  • Худший случай: O (n) (для 1 000 000).
  •   

Путешествующий продавец

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

Звучит просто? Подумай еще раз.

Если у вас есть 3 города A, B и C с дорогами между всеми парами, то вы можете пойти:

  
  • A → B → C
  •   
  • A → C → B
  •   
  • B → C → A
  •   
  • B → A → C
  •   
  • C → A → B
  •   
  • C → B → A
  •   

Ну, на самом деле есть нечто меньшее, потому что некоторые из них эквивалентны (A → B → C и C → B → A эквивалентны, например, потому что они используют одни и те же дороги, только наоборот).

На самом деле есть 3 варианта.

  
  • Отнесите это в 4 города, и у вас будет (iirc) 12 возможностей.
  •   
  • С 5 - 60.
  •   
  • 6 становится 360.
  •   

Это функция математической операции, называемой факториалом . В основном:

  
  • 5! = 5 × 4 × 3 × 2 × 1 = 120
  •   
  • 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
  •   
  • 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
  •   
  • ...
  •   
  • 25! = 25 × 24 ×… × 2 × 1 = 15,511,210,043,330,985,984,000,000
  •   
  • ...
  •   
  • 50! = 50 × 49 ×… × 2 × 1 = 3,04140932 × 10 64
  •   

Таким образом, главная проблема задачи коммивояжера - O (n!) или факторная или комбинаторная сложность .

К тому времени, когда вы доберетесь до 200 городов, во вселенной не останется времени для решения проблемы с традиционными компьютерами.

О чем подумать.

Полиномиальное время

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

O (n), O (n 2 ) и т. д. - все полиномиальное время. Некоторые проблемы не могут быть решены за полиномиальное время. Из-за этого в мире используются определенные вещи. Криптография с открытым ключом является ярким примером. В вычислительном отношении трудно найти два простых фактора очень большого числа. Если бы это было не так, мы не могли бы использовать системы открытых ключей, которые мы используем.

В любом случае, это все для моего (надеюсь простого английского) объяснения Big O (исправлено).

    

6390
2017-06-30 03: 17: 23Z
  1. В то время как другие ответы сосредоточены на объяснении различий между O (1), O (n ^ 2) и др .... ваш тот, который подробно описывает, как алгоритмы можно классифицировать по n ^ 2, nlog (n) и т. д. +1 за хороший ответ, который также помог мне понять нотацию Big O
    2009-01-28 11: 42: 39Z
  2. можно добавить, что big-O представляет верхнюю границу (заданную алгоритмом), big-Omega - нижнюю границу (обычно указанную в качестве доказательства, независимого от конкретный алгоритм) и big-Theta означает, что известен «оптимальный» алгоритм, достигающий этой нижней границы.
    2009-02-02 19: 16: 22Z
  3. Это хорошо, если вы ищете самый длинный ответ, но не тот, который лучше всего объясняет Big-O простым способом.
    2010-07-16 18: 21: 59Z
  4. - 1: Это явно неверно: _ "BigOh - относительное представление сложности алгоритма". Нет. BigOh является асимптотической верхней границей и существует довольно хорошо, независимо от компьютерных наук. O (n) является линейным. Нет, ты путаешь BigOh с тэтой. log n является O (n). 1 является O (n). Количество возражений против этого ответа (и комментариев), который делает основную ошибку, путая Тету с BigOh, весьма смущает ...
    2011-05-24 04: 44: 04Z
  5. "К тому времени, когда вы доберетесь до 200 городов, во вселенной не останется времени для решения проблемы с традиционными компьютерами." Когда наступит конец вселенной?
    2012-06-18 10: 43: 39Z

Показывает, как масштабируется алгоритм.

O (n 2 ) : известен как квадратичная сложность

  • 1 элемент: 1 секунда
  • 10 элементов: 100 секунд
  • 100 записей: 10000 секунд

Обратите внимание, что количество элементов увеличивается в 10 раз, но время увеличивается в 10 2 . В основном, n = 10, и поэтому O (n 2 ) дает нам коэффициент масштабирования n 2 , который составляет 10 2 .

O (n) : известен как линейная сложность

  • 1 элемент: 1 секунда
  • 10 элементов: 10 секунд
  • 100 записей: 100 секунд

На этот раз количество предметов увеличивается в 10 раз, как и время. n = 10, и поэтому коэффициент масштабирования O (n) равен 10.

O (1) : известен как постоянная сложность

  • 1 элемент: 1 секунда
  • 10 элементов: 1 секунда
  • 100 элементов: 1 секунда

Количество элементов все еще увеличивается в 10 раз, но коэффициент масштабирования O (1) всегда равен 1.

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

  • 1 элемент: 1 секунда
  • 10 элементов: 2 секунды
  • 100 записей: 3 секунды
  • 1000 элементов: 4 секунды
  • 10000 пунктов: 5 секунд

Количество вычислений увеличивается только путем записи входного значения. Таким образом, в этом случае, предполагая, что каждое вычисление занимает 1 секунду, журнал ввода n - это требуемое время, следовательно, log n.

В этом суть. Они уменьшают математику, поэтому она может быть не совсем n 2 или чем-то еще, как они говорят, но это будет доминирующим фактором в масштабировании.

    
696
2014-10-13 16: 53: 20Z
  1. что конкретно означает это определение? (Количество элементов все еще увеличивается в 10 раз, но коэффициент масштабирования O (1) всегда равен 1.)
    2010-03-25 22: 10: 14Z
  2. Не секунды, операции. Кроме того, вы пропустили факториальное и логарифмическое время.
    2010-07-17 01: 27: 04Z
  3. Это не очень хорошо объясняет, что O (n ^ 2) может описывать алгоритм, который работает точно .01 * n ^ 2 + 999999 * n + 999999 Важно знать, что алгоритмы сравниваются с использованием этой шкалы, и что сравнение работает, когда n «достаточно велико». Timsort Python фактически использует сортировку вставки (наихудший /средний случай O (n ^ 2)) для небольших массивов из-за того, что он имеет небольшие накладные расходы.
    2012-05-21 23: 14: 36Z
  4. Этот ответ также путает нотацию О и тета. Функция n, которая возвращает 1 для всех своих входов (обычно просто записываемых как 1), фактически находится в O (n ^ 2) (даже если она также в O (1)). Точно так же алгоритм, который должен сделать только один шаг, который занимает постоянное количество времени, также считается алгоритмом O (1), но также и алгоритмом O (n) и O (n ^ 2)гектометр Но, возможно, математики и компьютерные ученые не согласны с определением: - /.
    2013-08-08 11: 11: 24Z
  5. Логарифмическая сложность O (log n), рассматриваемая в этом ответе, относится к основанию 10. Обычно стандартом является вычисление с основанием 2. Следует иметь в виду этот факт. и не следует путать. Также, как упомянуто @ChrisCharabaruk, сложность обозначает количество операций, а не секунд.
    2016-02-17 06: 46: 36Z

Нотация Big-O (также называемая нотацией «асимптотического роста») - это то, на что «em» похожи функции, когда вы игнорируете постоянные множители и вещи рядом с источником . Мы используем его, чтобы поговорить о том, как масштабировать вещи .

Основы

для "достаточно" больших входов ...

  •  f(x) ∈ O(upperbound) означает f "растет не быстрее, чем" upperbound
  •  f(x) ∈ Ɵ(justlikethis) означает f "растет точно так же, как" justlikethis
  •  f(x) ∈ Ω(lowerbound) означает f "растет не медленнее, чем" lowerbound
Обозначение

big-O не заботится о постоянных факторах: говорят, что функция 9x² «растет точно так же, как» 10x². Также нотация big-O асимптотики не заботится о неасимптотических вещах («вещи рядом с источником» или «что происходит, когда размер проблемы мал»): функция 10x² Говорят, "расти точно так же, как" 10x² - x + 2.

Почему вы хотите игнорировать меньшие части уравнения? Потому что они сильно затмеваются большими частями уравнения, если учесть все большие и большие масштабы; их вклад становится незначительным и не имеет значения. (См. Пример раздела.)

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

 
actualAlgorithmTime(N) ∈ O(bound(N))
                                       e.g. "time to mergesort N elements 
                                             is O(N log(N))"

... это означает, что для "достаточно больших" размеров задач N (если мы игнорируем вещи возле источника), существует некоторая постоянная (например, 2.5, полностью сделано) так, что:

 
actualAlgorithmTime(N)                 e.g. "mergesort_duration(N)       "
────────────────────── < constant            ───────────────────── < 2.5 
       bound(N)                                    N log(N)         

Есть много вариантов констант; часто «лучший» выбор известен как «постоянный фактор» алгоритма ... но мы часто игнорируем его, как игнорируем не самые большие термины (см. раздел «Постоянные факторы», почему они обычно не имеют значения). Вы также можете думать о приведенном выше уравнении как о границе, говоря: « В худшем случае время, которое оно занимает, никогда не будет хуже, чем примерно N*log(N), с коэффициентом 2,5 (постоянный фактор, который нас не волнует» много о) ".

В целом, O(...) является наиболее полезным, потому что мы часто заботимся о худшем поведении. Если f(x) представляет что-то «плохое», например, использование процессора или памяти, то «f(x) ∈ O(upperbound)» означает «upperbound - наихудший сценарий использования процессора /памяти».

Приложения

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

  • количество возможных рукопожатий среди N человек на вечеринке (Ɵ(N²), в частности N(N-1)/2, но важно то, что оно «масштабируется как» )
  • вероятностное ожидаемое количество людей, которые рассматривают вирусный маркетинг как функцию времени
  • как задержка веб-сайта изменяется в зависимости от количества процессорных блоков в процессоре, графическом процессоре или компьютерном кластере
  • как тепловая мощность на процессоре умирает в зависимости от количества транзисторов, напряжения и т. д.
  • сколько времени нужно запустить алгоритму в зависимости от размера ввода
  • сколько места нужно запустить алгоритму в зависимости от размера ввода

Пример сильный> р>

В приведенном выше примере рукопожатия все в комнате пожимают друг другу руки. В этом примере #handshakes ∈ Ɵ(N²). Почему?

Сделайте небольшое резервное копирование: количество рукопожатий в точности равно n-Choose-2 или N*(N-1)/2 (каждый из N человек пожимает руки N-1 другим людям, но это двойное количество рукопожатий, так что разделите на 2): р>

 каждый рукопожатие всех остальных. Изображение и лицензия на каждую википедию /статью Викимедиа объединяет статью «Полный график». '> </a> <a href= матрица смежности

Однако для очень большого числа людей линейный член N является карликовым и фактически добавляет 0 к отношению (на диаграмме: доля пустых блоков по диагонали по сравнению с общими блоками уменьшается по мере увеличения числа участников). ). Поэтому масштабирование составляет order N², или количество рукопожатий «растет как N²».

 
#handshakes(N)
────────────── ≈ 1/2
     N²

Это как если бы пустых полей на диагонали диаграммы (N * (N-1) /2 галочки) даже не было (N 2 галочек асимптотически).

(временное отступление от «простого английского» :) Если вы хотите доказать это себе, вы можете выполнить некоторую простую алгебру отношения, чтобы разделить его на несколько терминов (lim означает «рассматривается в пределе», просто игнорируйте его, если вы его еще не видели, это просто обозначение «а N действительно очень большой»):

 
    N²/2 - N/2         (N²)/2   N/2         1/2
lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2
N→∞     N²       N→∞     N²     N²      N→∞  1
                               ┕━━━┙
             this is 0 in the limit of N→∞:
             graph it, or plug in a really large number for N

tl; dr: количество рукопожатий «выглядит как» x² настолько для больших значений, что если бы мы записали соотношение # handshakes /x², тот факт, что нам не нужен ровно рукопожатия x² даже не будут отображаться в десятичном виде в течение сколь угодно большого времени.

  

например. для х = 1 миллион, отношение # рукопожатия /х²: 0,499999 ...

Построение интуиции

Это позволяет нам делать заявления вроде ...

  

"Для достаточно большого inputize = N, независимо от того, каков постоянный коэффициент, если я удваиваю размер ввода ...

  • ... я удваиваю время, затрачиваемое алгоритмом O (N) ("линейное время"). "
      

    N → (2N) = 2 ( N )

  • ... я делаю двойной квадрат (в четыре раза) времени, которое занимает алгоритм O (N²) ("квадратичное время"). " (например, задача 100x как большая занимает 100² = 10000x как долго ... возможно неустойчивое)
      

    → (2N) ² = 4 ()

  • ... я дважды (в восьмеричном выражении) удваиваю время, затрачиваемое алгоритмом O (N³) ("кубическое время"). " (например, задача 100x большого размера занимает 100³ = 1000000x длинного ... очень неустойчивое)
      

    cN³ → c (2N) ³ = 8 ( cN³ )

  • ... я добавляю фиксированную сумму ко времени, которое занимает алгоритм O (log (N)) ("логарифмическое время"). " (дешево!)
      

    c log (N) → c log (2N) = (c log (2)) + ( c log (N) ) = (фиксированная сумма) + ( c log (N) )

  • ... я не меняю время, которое занимает алгоритм O (1) ("постоянное время"). " (самый дешевый!)
      

    c * 1 c * 1

  • ... I "(в основном) удваивает" время, которое занимает алгоритм O (N log (N)). " (довольно часто)
      

    он меньше O (N 1.000001 ), который вы можете назвать в основном линейным

  • ... я смешно увеличиваю время, которое занимает алгоритм O (2 N ) ("экспоненциальное время"). " (вы удвоите (или утроите и т. д.) время просто увеличив проблему на единицу)
      

    2 N → 2 2N = (4 N ) ......... ... поставить другой путь ...... 2 N → 2 N + 1 = 2 N 2 1 = 2 2 N

[для математически наклонных, вы можете навести курсор мыши на спойлеры для незначительных признаков]

(с благодарностью https://stackoverflow.com/a/487292/711085 )

(технически постоянный фактор может иметь значение в некоторых более эзотерических примерах, но я сформулировал выше (например, в журнале (N)), что это не так)

Это все те порядки роста, которые программисты и прикладные компьютерные ученые используют как ориентиры. Они видят это все время. (Таким образом, хотя вы могли бы технически подумать: «Удвоение ввода делает алгоритм O (√N) в 1,414 раз медленнее», лучше думать об этом как «это хуже, чем логарифмический, но лучше, чем линейный».)

Постоянные факторы

Обычно нас не волнуют конкретные константные факторы, потому что они не влияют на рост функции. Например, два алгоритма могут занять O(N) времени, но один может быть в два раза медленнее другого. Мы обычно не слишком заботимся, если фактор не очень велик, так как оптимизация - сложная задача ( Когда происходит оптимизация преждевременный? ); также простой акт выбора algorithm с лучшим big-O часто улучшает производительность на порядки.

Некоторые асимптотически превосходные алгоритмы (например, не сравниваемые O(N log(log(N))) сортировки) могут иметь такой большой постоянный коэффициент (например, 100000*N log(log(N))) или относительно большие издержки, как O(N log(log(N))) со скрытым + 100*N, что их редко стоит использовать даже на " большие данные ".

Почему O (N) иногда - лучшее, что вы можете сделать, т. е. зачем нам структуры данных

O(N) алгоритмы в некотором смысле являются «лучшими» алгоритмами, если вам нужно прочитать все ваши данные. Сам акт чтения группы данных - это операция O(N). Загрузка его в память обычно занимает O(N) (или быстрее, если у вас есть аппаратная поддержка, или совсем нет времени, если вы уже прочитали данные). Однако если вы дотронетесь или даже посмотрите на каждый фрагмент данных (или даже на любой другой фрагмент данных), вашему алгоритму потребуется O(N) раз, чтобы выполнить этот поиск. Неважно, сколько времени займет ваш фактический алгоритм, он будет по крайней мере O(N), потому что он потратил это время на просмотр всех данных.

То же самое можно сказать и о самом акте письма . Все алгоритмы, которые распечатывают N вещей, будут занимать N времени, потому что выходной результат, по крайней мере, такой длинный (например, распечатка всех перестановок (способов перестановки) набора из N игральных карт является факториальной: O(N!)).

Это мотивирует использование структур данных : структура данных требует чтения данных только один раз (обычно O(N) раз) плюс некоторое произвольное количество предварительной обработки (например, O(N) или O(N log(N)) или O(N²)), которую мы пытаемся оставаться маленьким После этого изменение структуры данных (вставки /удаления /и т. Д.) И выполнение запросов к данным занимают очень мало времени, например O(1) или O(log(N)). Затем вы приступаете к выполнению большого количества запросов! В общем, чем больше работы вы готовы выполнить раньше времени, тем меньше работы вам придется выполнять позже.

Например, скажем, у вас были координаты широты и долготы миллионов отрезков дорог, и вы хотели найти все перекрестки улиц.

  • Наивный метод. Если у вас есть координаты пересечения улиц и вы хотите исследовать близлежащие улицы, вам придется каждый раз проходить миллионы отрезков и проверять каждый из них на смежность.
  • Если вам нужно сделать это только один раз, не будет проблемой, если вы будете выполнять наивный метод работы O(N) только один раз, но если вы захотите сделать это много раз (в данном случае N раз, один раз для каждый сегмент), мы должны были бы выполнить O(N²) работ или 1000000² = 1000000000000 операций. Не хорошо (современный компьютер может выполнять около миллиарда операций в секунду).
  • Если мы используем простую структуру, называемую хеш-таблицей (справочная таблица с мгновенной скоростью, также известная как хэш-карта или словарь), мы платим небольшую стоимость, предварительно обработав все за O(N) раз. После этого в среднем требуется только постоянное время, чтобы найти что-то по его ключу (в этом случае наш ключ - это координаты широты и долготы, округленные в сетку; мы ищем соседние сеточные пространства, которых всего 9, что является константа).
  • Наша задача перешла от неосуществимого O(N²) к управляемому O(N), и все, что нам нужно было сделать, это заплатить небольшую плату за создание хеш-таблицы.
  • аналогия : аналогия в данном конкретном случае представляет собой головоломку: мы создали структуру данных, которая использует некоторые свойства данных. Если наши сегменты дороги похожи на кусочки головоломки, мы группируем их по цвету и рисунку. Затем мы используем это, чтобы избежать дополнительной работы позже (сравнивая кусочки пазла одинакового цвета друг с другом, а не с каждым другим кусочком головоломки).

Мораль этой истории: структура данных позволяет нам ускорить работу. Даже более продвинутые структуры данных позволяют невероятно умным образом комбинировать, задерживать или даже игнорировать операции. Разные проблемы будут иметь разные аналогии, но все они будут включать в себя организацию данных таким образом, чтобы использовать некоторую структуру, которая нам небезразлична, или которую мы искусственно навязали ей для учета. Мы работаем раньше времени (в основном, планируя и организуя), и теперь повторять задачи намного проще!

Практический пример: визуализация порядка роста при кодировании

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

Основы: всякий раз, когда мы взаимодействуем с каждым элементом в коллекции размера A (таким как массив, набор, все ключи карты и т. д.), или выполняем итерации цикла, то есть множитель размера А. Почему я говорю «мультипликативный фактор»? - потому что циклы и функции (почти по определению)иметь мультипликативное время выполнения: количество итераций, время работы в цикле (или для функций: количество вызовов функции, время работы в функции). (Это справедливо, если мы не делаем ничего сложного, например, пропускаем циклы или рано выходим из цикла, или меняем поток управления в функции на основе аргументов, что очень часто встречается.) Вот несколько примеров методов визуализации с сопровождающим псевдокодом. р>

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

 
for(i=0; i<A; i++)        // A * ...
    some O(1) operation     // 1

--> A*1 --> O(A) time

visualization:

|<------ A ------->|
1 2 3 4 5 x x ... x

other languages, multiplying orders of growth:
  javascript, O(A) time and space
    someListOfSizeA.map((x,i) => [x,i])               
  python, O(rows*cols) time and space
    [[r*c for c in range(cols)] for r in range(rows)]

Пример 2:

 
for every x in listOfSizeA:   // A * (...
    some O(1) operation         // 1
    some O(B) operation         // B
    for every y in listOfSizeC: // C * (...
        some O(1) operation       // 1))

--> O(A*(1 + B + C))
    O(A*(B+C))        (1 is dwarfed)

visualization:

|<------ A ------->|
1 x x x x x x ... x

2 x x x x x x ... x ^
3 x x x x x x ... x |
4 x x x x x x ... x |
5 x x x x x x ... x B  <-- A*B
x x x x x x x ... x |
................... |
x x x x x x x ... x v

x x x x x x x ... x ^
x x x x x x x ... x |
x x x x x x x ... x |
x x x x x x x ... x C  <-- A*C
x x x x x x x ... x |
................... |
x x x x x x x ... x v

Пример 3:

 
function nSquaredFunction(n) {
    total = 0
    for i in 1..n:        // N *
        for j in 1..n:      // N *
            total += i*k      // 1
    return total
}
// O(n^2)

function nCubedFunction(a) {
    for i in 1..n:                // A *
        print(nSquaredFunction(a))  // A^2
}
// O(a^3)

Если мы сделаем что-то немного сложное, вы все равно сможете визуально представить, что происходит:

 
for x in range(A):
    for y in range(1..x):
        simpleOperation(x*y)

x x x x x x x x x x |
x x x x x x x x x   |
x x x x x x x x     |
x x x x x x x       |
x x x x x x         |
x x x x x           |
x x x x             |
x x x               |
x x                 |
x___________________|

Здесь важен наименьший узнаваемый контур, который вы можете нарисовать; треугольник - это двумерная форма (0,5 A ^ 2), точно так же, как квадрат - это двумерная форма (A ^ 2); постоянный множитель два здесь остается в асимптотическом соотношении между ними, однако мы игнорируем его, как и все факторы ... (У этой техники есть некоторые прискорбные нюансы, в которые я не вхожу; она может ввести вас в заблуждение.) р>

Конечно, это не значит, что циклы и функции плохие; напротив, они являются строительными блоками современных языков программирования, и мы их любим. Однако мы видим, что способ, которым мы плетем циклы, функции и условия вместе с нашими данными (поток управления и т. Д.), Имитирует использование нашей программы во времени и пространстве! Если использование времени и пространства становится проблемой, то тогда мы прибегаем к хитрости и находим простой алгоритм или структуру данных, которые мы не рассматривали, чтобы каким-то образом уменьшить порядок роста. Тем не менее, эти методы визуализации (хотя они не всегда работают) могут дать вам наивное предположение в худшем случае.

Вот еще одна вещь, которую мы можем распознать визуально:

 
<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x
x x x x x x x x
x x x x
x x
x

Мы можем просто изменить это и увидеть, что это O (N):

 
<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x|x x x x x x x x|x x x x|x x|x

Или, может быть, вы делаете log (N) проходов данных, для O (N * log (N)) общего времени:

 
   <----------------------------- N ----------------------------->
 ^  x x x x x x x x x x x x x x x x|x x x x x x x x x x x x x x x x
 |  x x x x x x x x|x x x x x x x x|x x x x x x x x|x x x x x x x x
lgN x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x
 |  x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x
 v  x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x

Безотносительно, но стоит упомянуть еще раз: если мы выполняем хеш (например, поиск по словарю /хеш-таблице), то это фактор O (1). Это довольно быстро.

 
[myDictionary.has(x) for x in listOfSizeA]
 \----- O(1) ------/    

--> A*1 --> O(A)

Если мы делаем что-то очень сложное, например, с помощью рекурсивной функции или алгоритма «разделяй и властвуй», вы можете использовать Основная теорема (обычно работает) или, в смешных случаях, теорема Акра-Бацци (почти всегда работает) вы посмотрите время выполнения вашего алгоритма в Википедии.

Но программисты так не думают, потому что в конечном итоге интуиция алгоритма просто становится второй натурой. Вы начнете кодировать что-то неэффективное и сразу же подумаете: «Я делаю что-то крайне неэффективное? ». Если ответ «да» И вы предвидите, что это действительно имеет значение, тогда вы можете сделать шаг назад и подумать о различных хитростях, чтобы заставить вещи работать быстрее (ответ почти всегда «использовать хеш-таблицу», редко «использовать дерево», и очень редко что-то более сложное).

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

Существует также понятие «амортизированный» и /или «средний случай» (обратите внимание, что они разные).

Средний регистр . Это не более, чем использование обозначения big-O для ожидаемого значения функции, а не самой функции. В обычном случае, когда вы считаете, что все входные данные одинаково вероятны, средний случай - это просто среднее время выполнения. Например, при быстрой сортировке, даже если наихудший случай равен O(N^2) для некоторых действительно плохих входных данных, средний случай - это обычный O(N log(N)) (действительно плохих входных данных очень мало, поэтому их мало, и мы не замечаем их в среднем случае ). р>

Амортизированный наихудший случай . Некоторые структуры данных могут иметь сложность наихудшего случая, которая является большой, но гарантируйте, что при выполнении многих из этих операций средний объем выполняемой вами работы будет лучше чем в худшем случае. Например, у вас может быть структура данных, которая обычно занимает O(1) постоянных времени. Тем не менее, иногда это будет «сбой» и займет O(N) раз для одной случайной операции, потому что, возможно, ему нужно будет провести какую-то бухгалтерию или сборку мусора или что-то в этом роде ... но он обещает вам, что если он сделает сбой, он больше не будет сбивать для Еще больше операций. В худшем случае стоимость по-прежнему составляет O(N) на операцию, но амортизированная стоимость для многих запусков составляет O(N)/N = O(1) на операцию. Поскольку крупные операции достаточно редки, можно считать, что огромное количество случайных работ сливается с остальной работой как постоянный фактор. Мы говорим, что работа «амортизируется» по достаточно большому количеству вызовов, что она асимптотически исчезает.

  

Аналогия для амортизированного анализа:

Ты водишь машину. Иногда вам нужно потратить 10 минут на   АЗС, а затем потратить 1 минуту, заправляя бак газом.   Если вы делали это каждый раз, когда ездили на машине куда-либо (потратить 10   минут езды до заправки, потратьте несколько секунд на заполнение   доля галлона), это было бы очень неэффективно. Но если вы заполните   один раз в несколько дней, 11 минут потратили на   АЗС «амортизируется» за достаточно большое количество поездок,   что вы можете игнорировать это и делать вид, что все ваши поездки были, возможно, на 5% длиннее.

Сравнение среднего и амортизированного наихудшего случая:

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

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

И средний случай, и амортизация являются невероятно полезными инструментами для размышлений и проектирования с учетом масштабирования.

(см. Разница между средним случаем и амортизированным анализом , если вы заинтересованы в этой подтеме.)

Многомерный биг-О

В большинстве случаев люди не понимают, что на работе более одной переменной. Например, в алгоритме поиска строки ваш алгоритм может занять время O([length of text] + [length of query]), то есть он линейный по двум переменным, таким как O(N+M). Другие более наивные алгоритмы могут быть O([length of text]*[length of query]) или O(N*M). Игнорирование нескольких переменных является одним из наиболее распространенных недостатков, которые я вижу в анализе алгоритмов, и может помешать вам при разработке алгоритма.

Вся история

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

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

  • Если вы сортируете что-то вроде 5 элементов, вы не хотите использовать быструю быструю сортировку O(N log(N)); Вы хотите использовать сортировку вставкой, которая хорошо работает на небольших входах. Такие ситуации часто встречаются в алгоритмах «разделяй и властвуй», где вы разбиваете задачу на все более мелкие подзадачи, такие как рекурсивная сортировка, быстрые преобразования Фурье или умножение матриц.
  • Если некоторые значения эффективно ограничены из-за какого-то скрытого факта (например, среднее человеческое имя мягко ограничено, возможно, 40 буквами, а человеческий возраст мягко ограничен около 150). Вы также можете наложить ограничения на ввод, чтобы эффективно сделать условия постоянными.

На практике даже среди алгоритмов, которые имеют одинаковую или сходную асимптотическую производительность, их относительные достоинства могут фактически зависеть от других факторов, таких как: другие факторы производительности (quicksort и mergesort равны O(N log(N)), но быстрая сортировка использует преимущества кэшей ЦП ); соображения неэффективности, такие как простота реализации; доступна ли библиотека, насколько авторитетна и поддерживается библиотека.

Программы также будут работать медленнее на компьютере с частотой 500 МГц и 2 ГГц. Мы на самом деле не рассматриваем это как часть границ ресурсапотому что мы думаем о масштабировании в терминах машинных ресурсов (например, за тактовый цикл), а не за реальную секунду. Однако есть похожие вещи, которые могут «тайно» влиять на производительность, например, работаете ли вы под эмуляцией или оптимизировал код компилятор или нет. Это может заставить некоторые базовые операции занимать больше времени (даже относительно друг друга) или даже асимптотически ускорять или замедлять некоторые операции (даже относительно друг друга). Эффект может быть небольшим или большим между различными реализациями и /или средой. Вы переключаете языки или машины, чтобы выполнить эту небольшую дополнительную работу? Это зависит от сотен других причин (необходимость, навыки, коллеги, производительность программиста, денежная ценность вашего времени, знакомство, обходные пути, почему бы не сборка или графический процессор и т. Д.), Которые могут быть важнее производительности. р>

Вышеуказанные проблемы, такие как язык программирования, почти никогда не рассматриваются как часть постоянного фактора (и не должны); все же нужно знать о них, потому что иногда (хотя редко) они могут влиять на вещи. Например, в cpython реализация очереди с собственным приоритетом асимптотически неоптимальна (O(log(N)), а не O(1) для выбранной вами вставки или find-min); Вы используете другую реализацию? Вероятно, нет, так как реализация C, вероятно, быстрее, и, возможно, есть другие подобные проблемы в других местах. Есть компромиссы; иногда они имеют значение, а иногда нет.

( изменить : на этом простое объяснение на английском языке заканчивается.)

Приложения по математике

Для полноты, точное определение нотации big-O выглядит следующим образом: f(x) ∈ O(g(x)) означает, что «f асимптотически ограничена сверху константой * g»: игнорируя все ниже некоторого конечного значения x, существует постоянная такой, что |f(x)| ≤ const * |g(x)|. (Остальные символы следующие: точно так же, как O означает ≤, Ω означает ≥. Существуют строчные варианты: o означает < и ω означает &gt ;.) f(x) ∈ Ɵ(g(x)) означает и f(x) ∈ O(g(x)), и f(x) ∈ Ω(g(x)) (верхний и нижний ограничены g ): существуют некоторые константы, такие что f всегда будет лежать в «полосе» между const1*g(x) и const2*g(x). Это самое сильное асимптотическое утверждение, которое вы можете сделать и примерно эквивалентное ==. (Извините, я решил отложить упоминание символов абсолютного значения до сих пор, для ясности; особенно потому, что я никогда не видел, чтобы отрицательные значения возникали в контексте информатики.)

Люди часто будут использовать = O(...), что, возможно, является более правильной нотацией «comp-sci» и совершенно законно для использования; «f = O (...)» читается как «f - порядок ... /f ограничен ххх ...» и рассматривается как «f - некоторое выражение, асимптотика которого ...». Меня учили использовать более строгий ∈ O(...). означает «элемент» (все еще читается как прежде). O(N²) на самом деле является классом эквивалентности , то есть набором вещей, которые мы считаем одинаковыми. В данном конкретном случае O(N²) содержит такие элементы, как {2 N², 3 N², 1/2 N², 2 N² + log(N), - N² + N^1.9, ...} и является бесконечно большим, но это все еще набор. Обозначение = может быть более распространенным и даже используется в работах всемирно известных компьютерных ученых. Кроме того, часто случается, что в случайной обстановке люди говорят O(...), имея в виду Ɵ(...); это технически верно, поскольку набор вещей Ɵ(exactlyThis) является подмножеством O(noGreaterThanThis) ... и его легче набирать. ; -) р>     

381
2018-11-14 08: 13: 05Z
  1. Отличный математический ответ, но ОП запросил простой английский ответ. Этот уровень математического описания не обязателен для понимания ответа, хотя для людей с особым математическим пониманием это может быть намного проще для понимания, чем «простой английский». Однако ОП попросил последнее.
    2013-07-02 22: 19: 52Z
  2. Предположительно, люди, кроме ОП, могут быть заинтересованы в ответах на этот вопрос. Разве это не руководящий принцип сайта?
    2014-02-03 18: 34: 33Z
  3. Хотя я могу, возможно, понять, почему люди могут просмотреть мой ответ и посчитать его слишком математическим (особенно «математика - это новый простой английский», непристойные замечания, поскольку они удалены), В первоначальном вопросе о big-O задается вопрос о функциях, поэтому я пытаюсь быть явным и говорить о функциях так, чтобы это дополняло простую английскую интуицию. Математика здесь часто может быть глоизучил или понял с математическим образованием в старшей школе. Я действительно чувствую, что люди могут посмотреть на Математические Приложения в конце, и предположить, что это часть ответа, когда просто посмотреть, как выглядит real математика.
    2015-04-03 04: 39: 54Z
  4. Это фантастический ответ; намного лучше ИМО, чем тот, который набрал наибольшее количество голосов. Требуемая «математика» не выходит за рамки того, что необходимо для понимания выражений в скобках после «O», чего не может избежать ни одно разумное объяснение, использующее какие-либо примеры.
    2016-04-27 15: 52: 07Z
  5. "f (x) ∈ O (верхняя граница) означает, что f" растет не быстрее, чем "верхняя граница", эти три просто сформулированные, но математически правильные объяснения большого О, Тета, и омега золотые Он описал мне простым языком, что пять разных источников не могли бы перевести меня без написания сложных математических выражений. Спасибо чувак! :)
    2016-09-04 22: 20: 10Z

РЕДАКТИРОВАТЬ: быстрое примечание, это почти наверняка сбивает с толку обозначение Big O (которое является верхним связаны с тэта-обозначением (которое является верхней и нижней границей). По моему опыту, это типично для дискуссий в неакадемических условиях. Извиняюсь за любую путаницу.

В одном предложении: по мере увеличения размера вашей работы, сколько времени потребуется для ее выполнения?

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

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

  • Использование линии стирки снаружи: при условии, что у вас бесконечно большой задний двор, стирка высыхает за O (1) раз. Как бы много у вас ни было, оно получит то же солнце и свежий воздух, поэтому размер не влияет на время сушки.

  • Использование сушилки для белья: вы кладете по 10 рубашек в каждую загрузку, а затем они заканчиваются через час. (Игнорируйте действительные цифры здесь - они не имеют значения.) Таким образом, сушка 50 рубашек занимает примерно в 5 раз больше, чем сушка 10 рубашек.

  • Помещение всего в вытяжной шкаф: если мы сложим все в одну большую кучу и просто позволим общему теплу сделать это, понадобится много времени, чтобы средние рубашки высохли. Я не хотел бы угадывать детали, но я подозреваю, что это по крайней мере O (N ^ 2) - когда вы увеличиваете загрузку при стирке, время сушки увеличивается быстрее.

Одним из важных аспектов нотации «большой O» является то, что не говорит, какой алгоритм будет быстрее для данного размера. Возьмите хеш-таблицу (строковый ключ, целочисленное значение) против массива пар (строка, целое число). Быстрее найти ключ в хеш-таблице или элемент в массиве на основе строки? (т. е. для массива: «найдите первый элемент, в котором строковая часть соответствует заданному ключу.») Хеш-таблицы обычно амортизируются (в среднем ~ = «)» O (1) - после того, как они настроены, это должно занять около в то же время, чтобы найти запись в таблице 100 записей, как и в таблице записей 1,000,000. Поиск элемента в массиве (на основе содержимого, а не индекса) является линейным, т. Е. O (N) - в среднем вам придется просмотреть половину записей.

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

    
241
2011-11-08 06: 15: 21Z
  1. Хеш-таблица требует запуска алгоритма для расчета индекса фактического массива (в зависимости от реализации). И массив просто имеет O (1), потому что это просто адрес. Но это не имеет ничего общего с вопросом, просто наблюдение:)
    2009-01-28 11: 29: 54Z
  2. Объяснение Джона имеет много общего с вопросом, который я думаю. это именно то, как можно объяснить это какой-то маме, и она, в конце концов, поймет это, я думаю :) Мне нравится пример одежды (в частности, последний, где он объясняет экспоненциальный рост сложности)
    2009-01-28 11: 32: 26Z
  3. Филип: я не говорю об адресе массива по индексу, я говорю о поиске подходящей записи в массиве. Не могли бы вы перечитать ответ и посмотреть, все еще неясно?
    2009-01-28 11: 35: 58Z
  4. @ Филип Экберг Я думаю, вы думаете о таблице с прямым адресом, где каждый индекс напрямую сопоставляется с ключом, следовательно, равен O (1), однако я считаю, что Джон речь идет о несортированном массиве пар ключ /вал, которые вы должны искать линейно.
    2011-07-29 09: 41: 13Z
  5. @ RBT: Нет, это не бинарный поиск. Он может сразу перейти к нужному хешу bucket , просто на основе преобразования из хеш-кода в индекс корзины. После этого поиск правильного хеш-кода в корзине может быть линейным или бинарным поиском ... но к этому времени вы уменьшите очень небольшую долю от общего размера словаря.
    2016-11-17 07: 57: 40Z

Big O описывает верхний предел поведения функции роста, например, времени выполнения программы, когда входные данные становятся большими.

Примеры: р>

  • O (n): если я удвою размер ввода, время выполнения удваивается

  • O (n 2 ): если размер ввода удваивается, время выполнения увеличивается в четыре раза

  • O (log n): если размер ввода удваивается, время выполнения увеличивается на один

  • O (2 n ): если размер ввода увеличивается на единицу, время выполнения удваивается

Размер ввода - это обычно пространство в битах, необходимое для представления ввода.

    
123
2014-01-11 11: 11: 19Z
  1. неверно! например O (n): если я удвою размер ввода, время выполнения умножится до конечной ненулевой константы. Я имею в виду O (n) = O (n + n)
    2010-05-16 11: 33: 33Z
  2. Я говорю о f в f (n) = O (g (n)), а не о g, как вы, кажется, понимаете.
    2010-08-06 12: 30: 15Z
  3. Я проголосовал, но последнее предложение не сильно мне помогает. Мы не часто говорим о «битах» при обсуждении или измерении Big (O).
    2011-09-05 16: 41: 08Z
  4. Вы должны добавить пример для O (n log n).
    2011-09-22 15: 50: 33Z
  5. Это не так ясно, по сути, он ведет себя немного хуже, чем O (n). Поэтому, если n удваивается, время выполнения умножается на коэффициент, несколько больший, чем 2.
    2011-09-23 06: 44: 50Z

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

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

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

ЯВо многих случаях «O» алгоритма попадает в один из следующих случаев:

  • O (1) . Время завершения одинаково, независимо от размера набора входных данных. Примером является доступ к элементу массива по индексу.
  • O (Log N) . Время выполнения увеличивается примерно в соответствии с log2 (n). Например, 1024 элемента занимают примерно вдвое больше, чем 32 элемента, потому что Log2 (1024) = 10 и Log2 (32) = 5. Примером является поиск элемента в дерево двоичного поиска (BST).
  • O (N) - время для завершения, которое масштабируется линейно с размером входного набора. Другими словами, если вы удвоите количество элементов во входном наборе, алгоритм займет примерно вдвое больше времени. Примером является подсчет количества элементов в связанном списке.
  • O (N Log N) . Время выполнения увеличивается на количество элементов, умноженное на результат Log2 (N). Примером этого являются сортировка кучи и быстрая сортировка .
  • O (N ^ 2) . Время завершения примерно равно квадрату количества элементов. Примером этого является пузырьковая сортировка .
  • O (N!) . Время до завершения - это факториал входного набора. Примером этого является решение проблемы грубой силы для коммивояжера .

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

    
102
2011-09-13 03: 08: 33Z
  1. cdiggins, что если у меня O (N /2) сложность, должна ли она быть O (N) или O (N /2), например, какая сложность, если я зациклюсь на половине строки.
    2017-05-12 15: 08: 29Z
  2. @ Melad Это пример умножения константы (0.5) на функцию. Это игнорируется, так как считается, что оно имеет значительный эффект для очень больших значений N.
    2017-05-18 19: 47: 55Z

Big O - это просто способ «выразить» себя обычным способом: «Сколько времени /пространства требуется для запуска моего кода?».

Вы можете часто видеть O (n), O (n 2 ), O (nlogn) и т. д., все это просто способы показать; Как меняется алгоритм?

O (n) означает, что Big O - это n, и теперь вы можете подумать: «Что такое n !?» Ну, "n" это количество элементов. Изображение, которое вы хотите найти для элемента в массиве. Вы должны смотреть на каждый элемент и как «Вы правильный элемент /предмет?» в худшем случае, элемент находится в последнем индексе, что означает, что это заняло столько же времени, сколько и элементов в списке, поэтому, чтобы быть обобщенным, мы говорим: «О, эй, n - справедливое заданное количество значений!» . р>

Итак, вы можете понять, что означает «n 2 », но чтобы быть еще более конкретным, поиграйте с мыслью, что у вас есть простой, самый простой из алгоритмов сортировки; BubbleSort. Этот алгоритм должен просматривать весь список для каждого элемента.

Мой список

    1 6 3

Поток здесь будет:

  • Сравните 1 и 6, какой самый большой? Хорошо, 6 находится в правильном положении, двигаясь вперед!
  • Сравните 6 и 3, о, 3 меньше! Давайте переместим это, хорошо, список изменился, нам нужно начать с самого начала!

Это O n 2 , потому что вам нужно просмотреть все элементы в списке, которые содержат "n" элементов. Для каждого элемента вы просматриваете все элементы еще раз, для сравнения, это также «n», поэтому для каждого элемента вы смотрите «n» раз, что означает n * n = n 2

Я надеюсь, что это так просто, как вы хотите.

Но помните, Big O - это просто способ испытать себя в манере времени и пространства.

    
79
2014-10-19 20: 47: 19Z
  1. для logN мы рассматриваем для цикла, работающего от 0 до N /2, а как насчет O (log log N)? Я имею в виду, как выглядит программа? извините за чистые математические навыки
2015-09-30 10: 52: 49Z

Big O описывает фундаментальную масштабируемость алгоритма.

Существует много информации, которую Big O не сообщает вам о данном алгоритме. Он сокращает до костей и дает только информацию о масштабируемой природе алгоритма, в частности о том, как использование ресурсов (время или память) алгоритма масштабируется в ответ на «размер ввода».

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

Почему это так важно? Поскольку программное обеспечение имеет дело с проблемами, которые могут различаться по размеру в три раза. Подумайте об этом на мгновение. Соотношение между скоростью, необходимой для полета на Луну, и скоростью ходьбы человека составляет менее 10000: 1, и это абсолютно ничтожно по сравнению с диапазоном входных размеров, с которым может столкнуться программное обеспечение. А поскольку программное обеспечение может сталкиваться с астрономическим диапазоном входных размеров, существует вероятность того, что сложность алгоритма Big O, его фундаментальная природа масштабирования, превосходит любые детали реализации.

Рассмотрим пример канонической сортировки. Bubble-sort - O (n 2 ), а merge-sort - O (n log n). Допустим, у вас есть два приложения сортировки: приложение A, которое использует пузырьковую сортировку, и приложение B, которое использует сортировку слиянием, и скажем, что при входных размерах около 30 элементов приложение A в 1000 раз быстрее, чем приложение B при сортировке. Если вам никогда не нужно сортировать более 30 элементов, тогда очевидно, что вы должны предпочесть приложение A, поскольку оно намного быстрее при таких размерах ввода. Однако, если вы обнаружите, что вам, возможно, придется отсортировать десять миллионов элементов, то вы ожидаете, что приложение B на самом деле окажется в тысячи раз быстрее, чем приложение A в этом случае, полностью из-за того, как масштабируется каждый алгоритм. р>     

53
2014-10-19 20: 48: 18Z

Вот простой английский бестиарий, который я склонен использовать при объяснении распространенных разновидностей Биг-О

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

O (1): сильный> р>

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

O (журнал n ):

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

О ( п ): сильный> р>

Стоимость решения проблемы пропорциональна размеру проблемы. Если ваша проблема удваивается в размерах, то стоимость решения удваивается. Поскольку большинство проблем необходимо каким-либо образом сканировать в компьютер, например, при вводе данных, чтении с диска или сетевом трафике, это обычно является доступным коэффициентом масштабирования.

O ( n log n ):

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

О ( п 2 ): сильный> р>

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

.

О (2 п ): сильный> р>

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

    
38
2014-03-10 06: 51: 52Z
  1. Не могли бы вы рассмотреть другую аналогию для O (1)? Инженер во мне хочет вытащить обсуждение импеданса RF из-за препятствий.
    2016-03-10 23: 02: 28Z
  2. Я использовал слово "несколько" по уважительной причине.
    2017-04-14 17: 12: 35Z

Big O - это мера того, сколько времени /пространства использует алгоритм относительно размера его входных данных.

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

Если алгоритм равен O (n 2 ), то время /пространство увеличиваются со скоростью его входного квадрата.

и т. д.

    
35
2014-10-19 20: 49: 11Z
  1. Дело не в космосе. Речь идет о сложности, что означает время.
    2009-01-28 11: 35: 02Z
  2. Я всегда считал, что это может быть время или пространство. но не об обоих одновременно.
    2009-01-28 12: 58: 59Z
  3. Сложность наиболее определенно может быть связана с пространством. Посмотрите на это: ru.wikipedia.org/wiki/PSPACE
    2010-08-08 15: 58: 49Z
  4. Этот ответ является наиболее "простым" здесь. Предыдущие предполагают, что читатели знают достаточно, чтобы понять их, но авторы не знают об этом. Они думают, что они просты и понятны, а это абсолютно не так. Написание большого количества текста с красивым форматом и создание причудливых искусственных примеров, которые трудны для людей, не относящихся к CS, непросто и просто, это просто привлекательно для стековых потоков, которые в основном являются людьми CS, чтобы проголосовать. Для объяснения термина CS на простом английском языке вообще не нужно ничего о коде и математике. +1 за этот ответ, хотя он все еще недостаточно хорош.
    2013-05-29 12: 36: 01Z
  5. Этот ответ допускает (общую) ошибку, предполагая, что f = O (g) означает, что f и g пропорциональны.
    2015-04-03 04: 38: 41Z

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

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

Поскольку они являются приблизительными, мы используем букву «О» (Big Oh) в выражении, чтобы договориться с читателем о том, что мы делаем грубое упрощение. (И чтобы никто не ошибочно считал, что выражение в любом случае точное).

Если вы прочитаете «О» как означающее «порядка» или «приблизительно», вы не ошибетесь. (Я думаю, что выбор Big-Oh, возможно, был попыткой юмора).

Единственное, что пытаются сделать выражения "Big-Oh", - это описать, насколько сильно программное обеспечение замедляется по мере того, как мы увеличиваем объем данных, которые должно обрабатывать программное обеспечение. Если мы удвоим объем данных, которые необходимо обработать, потребуется ли программе вдвое больше времени, чтобы завершить свою работу? Десять раз больше? На практике вы можете столкнуться с очень ограниченным числом выражений типа «большой О», и вам нужно о них беспокоиться:

Хорошее:

  •  O(1) Константа . Программа запускается одинаково независимо от размера ввода.
  •  O(log n) Логарифмический : время выполнения программы увеличивается только медленно, даже при большом увеличении размера ввода.

Плохо:

  •  O(n) Линейный . Время выполнения программы увеличивается пропорционально размеру ввода.
  •  O(n^k) Полином . - Время обработки увеличивается - как полиномиальная функция - с увеличением размера ввода.

... и безобразный:

  •  O(k^n) Экспоненциальная . Время выполнения программы очень быстро увеличивается даже при умеренном увеличении размера задачи - практично обрабатывать только небольшие наборы данных с помощью экспоненциальных алгоритмов.
  •  O(n!) Factorial . Время выполнения программы будет больше, чем вы можете позволить себе ждать чего угодно, кроме самых маленьких и самых банальных наборов данных.
31
2013-05-29 13: 51: 20Z
  1. Я также слышал термин Linearithmic - O(n log n), который можно считать хорошим.
    2013-05-29 18: 45: 06Z
  

Что такое простое английское объяснение Big O? С как можно меньшим количеством формального определения и простой математикой.

Простое английское объяснение потребности для обозначения Big-O:

Когда мы программируем, мы пытаемся решить проблему. То, что мы кодируем, называется алгоритмом. Обозначение Big O позволяет нам сравнивать производительность наших алгоритмов в худшем случае стандартизированным способом. Характеристики оборудования меняются со временем, а улучшения в оборудовании могут сократить время, необходимое для работы алгоритмов. Но замена оборудования не означает, что наш алгоритм улучшается или совершенствуется с течением времени, поскольку наш алгоритм остается тем же. Поэтому для того, чтобы мы могли сравнивать разные алгоритмы, чтобы определить, является ли один из них лучше или нет, мы используем обозначение Big O.

Простое английское объяснение обозначения Что Big O:

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

    
31
2013-10-07 14: 02: 21Z

Простой прямой ответ может быть следующим:

Большой O представляет наихудшее время /пространство для этого алгоритма. Алгоритм никогда не займет больше места /времени выше этого предела. Большой O представляет сложность времени /пространства в крайнем случае.

    
27
2014-03-14 16: 25: 08Z

Хорошо, мои 2цента.

Big-O, скорость увеличения ресурса, потребляемого программой, w.r.t. Проблема-экземпляр размера р>

Ресурс: может быть общим временем ЦП, может быть максимальным объемом ОЗУ. По умолчанию относится к времени процессора.

Скажите, что проблема в том, чтобы найти сумму,

 
int Sum(int*arr,int size){
      int sum=0;
      while(size-->0) 
         sum+=arr[size]; 

      return sum;
}

problem-instance = {5,10,15} == > задача-размер-экземпляра = 3, итерации в цикле = 3

problem-instance = {5,10,15,20,25} == > размер экземпляра задачи = 5 итераций в цикле = 5

При вводе размера «n» программа растет со скоростью «n» итераций в массиве. Следовательно, Big-O - это N, выраженное как O (n)

Скажите, что проблема в том, чтобы найти комбинацию,

 
    void Combination(int*arr,int size)
    { int outer=size,inner=size;
      while(outer -->0) {
        inner=size;
        while(inner -->0)
          cout<<arr[outer]<<"-"<<arr[inner]<<endl;
      }
    }

problem-instance = {5,10,15} == > размер экземпляра задачи = 3, всего итераций = 3 * 3 = 9

problem-instance = {5,10,15,20,25} == > размер экземпляра задачи = 5, итераций всего = 5 * 5 = 25

Для ввода размера «n» программа растет со скоростью «n * n» итераций в массиве. Следовательно, Big-O - это N 2 , выраженное как O (n 2 )

    
27
2014-10-19 20: 48: 48Z
  1. while (size-->0) Я надеюсь, что это больше не будет спрашивать.
    2013-06-18 14: 41: 28Z

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

Когда мы говорим, что некоторым алгоритмом является O (f (n)), мы говорим, что время выполнения (или пространство, необходимое) для этого алгоритма всегда меньше, чем некоторое постоянное время f (n).

Сказать, что бинарный поиск имеет время выполнения O (logn), означает, что существует некоторая константа c, которую вы можете умножить на log (n), которая всегда будет больше времени выполнения бинарного поиска. В этом случае вы всегда будете иметь некоторый постоянный коэффициент сравнения log (n).

Другими словами, где g (n) - время выполнения вашего алгоритма, мы говорим, что g (n) = O (f (n)), когда g (n) < = c * f (n), когда n &GT; k, где c и k - некоторые постоянные.

    
25
2010-07-17 02: 29: 35Z
  1. Мы можем использовать нотацию BigO для измерения как наихудшего, так и среднего случая. en.wikipedia.org/wiki/Big_O_notation
    2011-09-05 16: 36: 05Z
  

" Что такое простое английское объяснение Big O?   определение как можно более простой математики. "

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

  

Обозначение Big O просто говорит, сколько времени * может работать алгоритм,   в терминах только объем входных данных **.

(* в прекрасном, свободном от юнитов смысле времени!)
(** это то, что имеет значение, потому что люди всегда хотят больше а> живут ли они сегодня или завтра)

Ну, что такого замечательного в обозначении Big O, если это то, что он делает?

  • Практически, анализ Big O является настолько полезным и важным , потому что Big O прямо фокусируется на собственной сложности алгоритма и полностью игнорирует все, что является просто константой пропорциональности - например, движок JavaScript, скорость процессора, ваше интернет-соединение и все те вещи, которые быстро становятся смехотворно устаревшими, как модель T . Big O фокусируется на производительности только таким образом, который одинаково важен для людей, живущихв настоящем или будущем.

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

23
2013-08-24 06: 50: 03Z
  1. Когда меня просят объяснить что-то математическое без математики, это всегда личный вызов для меня, как добросовестного кандидата наук. математик и учитель, который считает, что такое действительно возможно. Будучи программистом, я надеюсь, что никто не возражает, что я нашел ответ на этот конкретный вопрос, без математики, вызовом, который был абсолютно неотразим.
    2013-08-15 02: 09: 07Z

Пример алгоритма (Java):

 
// given a list of integers L, and an integer K
public boolean simple_search(List<Integer> L, Integer K)
{
    // for each integer i in list L
    for (Integer i : L)
    {
        // if i is equal to K
        if (i == K)
        {
            return true;
        }
    }

    return false;
}

Описание алгоритма:

  • Этот алгоритм ищет список, элемент за элементом, ищет ключ,

  • Итерация каждого элемента в списке, если это ключ, затем верните True,

  • Если цикл завершился без поиска ключа, верните False.

Нотация Big-O представляет верхнюю границу сложности (время, пространство, ..)

Чтобы найти Big-O по сложности времени:

  • Рассчитайте, сколько времени (относительно размера ввода) занимает худший случай:

  • В худшем случае: ключ не существует в списке.

  • Время (в худшем случае) = 4n + 1

  • Время: O (4n + 1) = O (n) | в Big-O константы игнорируются

  • O (n) ~ Линейный

Существует также Big-Omega, которая представляет сложность лучшего случая:

  • Лучший случай: ключ является первым элементом.

  • Время (в лучшем случае) = 4

  • Время: Ω (4) = O (1) ~ Мгновенное \Константа

21
2018-05-18 10: 46: 20Z
  1. Откуда берется ваша константа 4?
    2014-07-04 13: 34: 45Z
  2. @ инициализация итератора Rod, сравнение итераторов, чтение итераторов, сравнение ключей .. Я думаю, что C будет лучше
    2014-07-06 11: 04: 55Z

Большой O

f (x) = O ( g (x)), когда x переходит к a (например, a = + ∞), означает, что есть функция k такой, что:

  1. f (x) = k (x) g (x)

  2. k ограничено в некоторой окрестности a (если a = + ∞, это означает, что существуют числа N и M такие, что для каждого x > N, | k (x ) | < M).

Другими словами, простым языком: f (x) = O ( g (x)), x → a, означает, что в окрестности a, f разлагается на произведение g и некоторой ограниченной функции.

Маленький o

Кстати, вот для сравнения определение маленького o.

f (x) = o ( g (x)), когда x означает, что существует функция k такая, что:

  1. f (x) = k (x) g (x)

  2. k (x) переходит в 0, когда x переходит к a.

Примеры

  • sin x = O (x), когда x → 0.

  • sin x = O (1), когда x → + ∞,

  • x 2 + x = O (x) при x → 0,

  • x 2 + x = O (x 2 ), когда x → + ∞,

  • ln (x) = o (x) = O (x), когда x → + ∞.

Внимание! В нотации со знаком равенства "=" используется "поддельное равенство": верно, что o (g (x)) = O (g (x)), но неверно что O (g (x)) = o (g (x)). Точно так же можно написать «ln (x) = o (x), когда x → + ∞», но формула «o (x) = ln (x)» не имеет смысла.

Еще примеры

  • O (1) = O (n) = O (n 2 ) когда n → + ∞ (но не наоборот, равенство «фальшивое»),

  • O (n) + O (n 2 ) = O (n 2 ), когда n → + ∞

  • O (O (n 2 )) = O (n 2 ), когда n → + ∞

  • O (n 2 ) O (n 3 ) = O (n 5 ), когда n → + ∞ р>

Вот статья в Википедии: https://en.wikipedia.org/wiki/Big_O_notation

    
18
2014-10-19 20: 50: 47Z
  1. Вы указываете "Big O" и "Small o", не объясняя, что они есть, вводите множество математических понятий, не сообщая, почему они важны, и ссылка на Википедию может быть в этом случае слишком очевидным для такого рода вопросов.
    2014-01-11 14: 54: 41Z
  2. @ AditSaxena Что вы имеете в виду "не объясняя, что они есть"? Я точно объяснил, что они есть. То есть «большой О» и «маленький о» сами по себе ничто, только формула типа «f (x) = O (g (x))» имеет значение, которое я объяснил (простым языком, но без определения конечно все необходимые вещи из курса исчисления). Иногда «O (f (x))» рассматривается как класс (фактически набор) всех функций «g (x)», таких что «g (x) = O (f (x))», но это дополнительный шаг, который не нужен для понимания основ.
    2014-01-11 18: 34: 54Z
  3. Хорошо, хорошо, есть слова, которые не являются простым английским, но это неизбежно, если только мне не придется включать все необходимые определения из математического анализа.
    2014-01-11 18: 38: 21Z
  4. Привет # Алексей, пожалуйста, взгляни на принятый ответ: он длинный, но хорошо сконструирован и хорошо отформатирован. Он начинается с простого определения без математического обоснования. При этом он вводит три «технических» слова, которые он объясняет немедленно (относительный, представление, сложность). Это происходит шаг за шагом при копании в этом поле.
    2014-01-12 22: 44: 07Z
  5. Большой O используется для понимания асимптотического поведения алгоритмов по той же причине, по которой он используется для понимания асимптотического поведения функций (асимптотическое поведение - это поведение вблизи бесконечности). Это удобное обозначение для сравнения сложной функции (фактического времени или пространства, занимаемого алгоритмом) с простыми (что-нибудь простое, обычно степенная функция) вблизи бесконечности или рядом с чем-либо еще. Я только объяснил, что это такое (дал определение). Как вычислить с большим O - это отдельная история, может быть, я добавлю несколько примеров, так как вы заинтересованы.
    2014-01-13 17: 23: 47Z

Обозначение Big O - это способ описания того, как быстро алгоритм будет работать при произвольном количестве входных параметров, которое мы назовем «n». Это полезно в компьютерных науках, потому что разные машины работают на разных скоростях, и просто сказать, что алгоритм занимает 5 секунд, мало что вам скажет, потому что, пока вы работаете в системе с процессором с тактовой частотой 4,5 ГГц, я могу работать 15-летняя система 800 МГц, которая может занять больше времени, независимо от алгоритма. Поэтому вместо того, чтобы указывать, насколько быстро алгоритм работает с точки зрения времени, мы говорим, насколько быстро он работает с точки зрения количества входных параметров, или «n». Описывая алгоритмы таким образом, мы можем сравнивать скорости алгоритмов без необходимости учитывать скорость самого компьютера.

    
18
2015-05-12 14: 02: 34Z

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

С помощью примеров это помогло получить базовые знания в моем черепахоподобном черепе, так что я думаю, что это 10-минутное чтение довольно спуска, чтобы направить вас в правильном направлении.

    
11
2013-01-15 20: 23: 20Z
  1. @ Уильям ... и люди, как правило, умирают от старости, виды вымирают, планеты становятся бесплодными и т. д.
    2013-05-30 05: 52: 12Z

Вы хотите знать все, что нужно знать о большой О? Я тоже.

Итак, чтобы говорить о большом О, я буду использовать слова, в которых есть только один удар. Один звук за слово. Маленькие слова быстрые. Вы знаете эти слова, и я тоже. Мы будем использовать слова с одним звуком. Они маленькие. Я уверен, что вы будете знать все слова, которые мы будем использовать!

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

Я не люблю ходить на работу. Я не люблю проводить время на работе. Если бы у меня был свой путь, я бы просто хотел играть и делать забавные вещи. Ты чувствуешь то же самое, что и я?

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

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

Теперь у меня есть работа. У меня есть этот список: один, два, три, четыре, пять, шесть. Я должен добавить все вещи в этом списке.

Вау, я ненавижу работу. Ну да ладно, я должен это сделать. Итак, я иду.

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

Так что давайте не будем делать работу. Давай ты и я просто подумаем, как это тяжело. Сколько работы мне нужно сделать, чтобы добавить шесть цифр?

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

Вот большая буква O, чтобы рассказать нам, насколько сложна эта математика.

Большой О говорит: мы должны сделать шесть добавок, чтобы решить эту проблему. Одно добавление, для каждой вещи от одного до шести. Шесть маленьких кусочков работы ... каждый кусочек работы - это одно дополнение.

Ну, я не буду делать работу, чтобы добавить их сейчас. Но я знаю, как это будет сложно. Было бы шесть добавляет.

О нет, теперь у меня есть больше работы. Sheesh. Кто делает такие вещи?!

Теперь они просят меня прибавить от одного до десяти! Зачем мне это делать? Я не хотел добавлять один к шести. Добавить от одного до десяти ... ну ... это было бы еще сложнее!

Насколько сложнее это будет? Сколько еще работы мне нужно сделать? Нужно ли мне больше или меньше шагов?

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

Я не хочу добавлять прямо сейчас. Я просто хочу подумать о том, как трудно это добавить. И, надеюсь, поиграю, как только смогу.

Чтобы добавить от одного до шести, это некоторая работа. Но вы видите, добавить от одного до десяти, это больше работы?

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

Теперь мы должны сделать новую работу. О нет. Мне вообще не нравится эта работа.

Новая работа: добавьте все от одного к n.

Подождите! Что это? Я пропустил это? Как я могу добавить от одного к n, если вы не скажете мне, что такое n?

Ну, я не знаю, что это такое. Мне не сказали. Были ли вы? Нет? Ну что ж. Так что мы не можем делать работу. Уф.

Но хотя мы не будем сейчас делать эту работу, мы можем догадаться, насколько это будет сложно, если бы мы знали n. Мы должны были бы сложить n вещей, верно? Конечно!

Теперь здесь идет большой O, и он расскажет нам, как тяжело эта работа. Он говорит: добавить все от одного к N, один за другим, есть O (n). Чтобы добавить все эти вещи, [я знаю, я должен добавить n раз.] [1] Это большой O! Он говорит нам, как трудно выполнять какую-то работу.

Для меня я думаю о большом О, как о большом медленном боссе. Он думает оработать, но он этого не делает. Он может сказать: «Эта работа быстрая». Или он может сказать: «Эта работа такая медленная и тяжелая!» Но он не делает работу. Он просто смотрит на работу, а затем говорит нам, сколько времени это может занять.

Я забочусь о большом О. Почему? Я не люблю работать! Никто не любит работать. Вот почему мы все любим большой O! Он говорит нам, как быстро мы можем работать. Он помогает нам подумать о том, как тяжелая работа.

Ой, больше работы. Теперь давайте не будем делать работу. Но давайте составим план, шаг за шагом.

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

Ergh. Это звучит как большая работа!

Как мы можем отсортировать эту колоду? У меня есть план.

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

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

В какой-то момент, в какое-то время перестановок не будет, и наша колода будет готова. Так много работы!

Ну, сколько это будет стоить, чтобы отсортировать карточки по этим правилам?

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

Большой О, помоги мне!

Входит большой O и говорит: для колоды из n карт сортировка будет выполнена за O (N в квадрате).

Почему он говорит n в квадрате?

Ну, вы знаете, n в квадрате - это n раз n. Теперь я понял: n карт проверено, вплоть до того, что может быть n раз в колоде. Это две петли, каждая из которых имеет n шагов. Это много работы в квадрате. Конечно, много работы!

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

Теперь вот где большой О - наш друг.

Большой O указывает на это: когда n становится большим, когда мы сортируем карточки, работа становится НАМНОГО БОЛЬШЕ тяжелее, чем старая работа «просто добавь эти вещи». Откуда мы это знаем?

Ну, если n становится действительно большим, нам все равно, что мы можем добавить к n или n в квадрате.

Для больших n квадрат n больше, чем n.

Big O говорит нам, что сортировать вещи сложнее, чем добавлять вещи. O (n в квадрате) больше, чем O (n) для больших n. Это означает: если n становится действительно большим, сортировка смешанной колоды из n вещей ДОЛЖНА занять больше времени, чем просто добавление n смешанных вещей.

Big O не решает работу за нас. Большой О говорит нам, насколько тяжелая работа.

У меня есть колода карт. Я их отсортировал. Вы помогли Спасибо.

Есть ли более быстрый способ сортировки карточек? Может ли большой О помочь нам?

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

В этом новом способе сортировки колоды мы не проверяем пары карт, как мы это делали некоторое время назад. Вот ваши новые правила сортировки этой колоды:

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

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

Три: я иду от конечной карты вверх и ищу карту ниже, чем сплайс-карта.

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

В какой-то момент этот цикл (от двух до трех) закончится. Он заканчивается, когда обе половины этого поиска встречаются у сплайс-карты. Затем мы только что добавили в колоду карту, которую вы выбрали в первом шаге. Теперь все карты рядом с началом находятся ниже, чем сплайс карты; и карты ближе к концу находятся выше, чем сплайс карты. Прикольный трюк!

Четыре (и это самое интересное): у меня сейчас две маленькие колоды: одна ниже, чем сплайс-карта, а другая - больше. Теперь я иду к первому шагу на каждой маленькой колоде! То есть я начинаю с первого шага на первой маленькой колоде, а когда эта работа закончена, я начинаю с первого шага на следующей маленькой колоде.

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

Как называется этот вид? Это называется Быстрая сортировка! Этот вид был сделан человеком по имени C. А. Р. Хоара и он назвал это быстрой сортировкой. Теперь быстрая сортировка привыкает постоянно!

Быстрая сортировка разбивает большие колоды на маленькие. То есть он разбивает большие задачи на маленькие.

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

Этот вид довольно быстрый. Как быстро? Большой O говорит нам: этот вид требует O (n log n) работы, в среднем.

Это более или менее быстро, чем первый сорт? Большой О, пожалуйста, помогите!

Первый вид был O (n в квадрате). Но Быстрая сортировка - это O (n log n). Вы знаете, что n log n меньше n в квадрате, для больших n, верно? Ну, вот как мы знаем, что быстрая сортировка быстрая!

Если вам нужно отсортировать колоду, как лучше? Ну, вы можете делать то, что вы хотите, но я бы выбрал быструю сортировку.

Почему я выбираю быструю сортировку? Я не люблю работать, конечно! Я хочу, чтобы работа была выполнена, как только я смогу ее выполнить.

Как узнать, что быстрая сортировка - это меньше работы? Я знаю, что O (n log n) меньше, чем O (n в квадрате). O более маленькие, поэтому быстрая сортировка - меньше работы!

Теперь вы знаете моего друга, Big O. Он помогает нам выполнять меньше работы. А если ты знаешь большой О, ты тоже можешь выполнять меньше работы!

Вы узнали все это со мной! Ты такой умный! Большое вам спасибо!

Теперь, когда работа закончена, поехали играть!

[1]: есть способ обмануть и добавить все вещи от одного до n, все за один раз. Какой-то ребенок по имени Гаусс узнал об этом, когда ему было восемь лет. Хотя я не такой умный, поэтому не спрашивайте меня, как он это сделал .

    
11
2016-03-10 23: 03: 36Z

Предположим, мы говорим об алгоритме A , который должен что-то делать с набором данных размером n .

Тогда O( <some expression X involving n> ) означает на простом английском:

  

Если вам не повезло при выполнении A, может потребоваться X (n) операций для   полная.

Как это бывает, существуют определенные функции (представьте их как реализации из X (n) ), которые обычно встречаются довольно часто. Они хорошо известны и их легко сравнивать (примеры: 1, Log N, N, N^2, N! и т. Д.).

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

В общем, нашей целью будет найти или структурировать алгоритм A таким образом, чтобы он имел функцию X(n), которая возвращает минимально возможное число.

    
9
2013-10-25 15: 11: 17Z

У меня есть более простой способ понять сложность времени Наиболее распространенной метрикой для вычисления сложности времени является нотация Big O. Это устраняет все постоянные факторы, так что время работы можно оценить по отношению к N, когда N приближается к бесконечности. В общем, вы можете думать об этом так:

 
statement;

Постоянно. Время выполнения оператора не изменится по отношению к N

 
for ( i = 0; i < N; i++ )
  statement;

Линейный. Время работы цикла прямо пропорционально N. Когда N удваивается, то же самое происходит и время работы.

 
for ( i = 0; i < N; i++ ) 
{
for ( j = 0; j < N; j++ )
  statement;
}

Является квадратичным Время работы двух петель пропорционально квадрату N. Когда N удваивается, время работы увеличивается на N * N.

 
while ( low <= high ) 
{
 mid = ( low + high ) / 2;
 if ( target < list[mid] )
 high = mid - 1;
 else if ( target > list[mid] )
  low = mid + 1;
else break;
}

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

 
void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

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

В общем, выполнение чего-либо с каждым элементом в одном измерении является линейным, выполнение чего-либо с каждым элементом в двух измерениях является квадратичным, а деление рабочей области пополам - логарифмическим. Есть и другие меры Big O, такие как кубическая, экспоненциальная и квадратный корень,но они не так распространены. Обозначение Big O описывается как O (), где есть мера. Алгоритм быстрой сортировки будет описан как O (N * log (N)).

Примечание. Ни в одном из них не учитывались показатели наилучшего, среднего и наихудшего случаев. У каждого будет своя нотация Big O. Также обратите внимание, что это ОЧЕНЬ упрощенное объяснение. Big O является наиболее распространенным, но он также более сложный, что я показал. Есть и другие обозначения, такие как большая омега, маленькая буква o и большая тэта. Вы, вероятно, не встретите их вне курса анализа алгоритма.

  • Подробнее читайте по адресу: Здесь
9
2015-09-15 13: 52: 39Z

Скажем, вы заказываете «Гарри Поттер: полная коллекция из 8 фильмов [Blu-ray]» от Amazon и одновременно скачиваете ту же коллекцию фильмов онлайн. Вы хотите проверить, какой метод быстрее. Доставка занимает почти день, а загрузка завершена примерно на 30 минут раньше. Большой! Так что это жесткая гонка.

Что если я закажу несколько Blu-ray фильмов, таких как «Властелин колец», «Сумерки», «Трилогия Темного рыцаря» и т. д., и загружу все фильмы онлайн одновременно? На этот раз доставка все еще занимает один день, но онлайн-загрузка занимает 3 дня. Для покупок в Интернете количество купленных товаров (входных данных) не влияет на время доставки. Выход постоянный. Мы называем это O (1) .

Для загрузки через Интернет время загрузки прямо пропорционально размеру файла фильма (входной). Мы называем это O (n) .

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

Примечание. Обозначение Big O представляет сценарий наихудшего случая алгоритма. Предположим, что O (1) и O (n) являются сценариями наихудшего случая в приведенном выше примере.

Ссылка : http://carlcheo.com/compsci

    
9
2015-12-06 06: 01: 13Z

Если у вас есть подходящее понятие бесконечности в вашей голове, тогда есть очень краткое описание:

  

Обозначение Big O говорит о стоимости решения бесконечно большой задачи.

И более того

  

Постоянные факторы незначительны

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

Однако можно обнаружить что-либо «большее», чем постоянный коэффициент.

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

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

    
8
2015-05-16 16: 02: 02Z
  

Что такое простое английское объяснение обозначения «Big O»?

Очень быстрое примечание.

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

  • «Большой О» делает две вещи:

    1. Оценивает, сколько шагов метода применяется вашим компьютером для выполнения задачи.
    2. Облегчить процесс сравнения с другими, чтобы определить, хорошо это или нет?
    3. «Большой О» достигает двух вышеупомянутых показателей со стандартизированным Notations.
  • Существует семь наиболее часто используемых обозначений

    1. O (1) означает, что ваш компьютер выполняет задание с шагом 1, это отлично, заказанный номер 1
    2. O (logN), означает, что ваш компьютер выполнил задание за logN шагов, это хорошо, Заказ № 2
    3. O (N), завершите задание, выполнив N шагов, честно, Заказ № 3
    4. O (NlogN), завершает задачу с O(NlogN) шагами, это нехорошо, Заказ № 4
    5. O (N ^ 2), выполни задачу за N^2 шагов, это плохо, приказ № 5
    6. O (2 ^ N), выполни задачу за 2^N шагов, это ужасно, Приказ № 6
    7. О (N!), выполни задачу за N! шагов, это ужасно, Приказ № 7

 введите описание изображения здесь

Предположим, вы получили обозначение O(N^2): не только вы уверены, что метод выполняет N * N шагов для выполнения задачи, но и видите, что он не так хорош, как O(NlogN) из своего ранжирования.

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

В CS набор шагов для выполнения задачи называется алгоритмами.
В терминологии нотация Big O используется для описания производительности или сложности алгоритма.

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

Big-Ω ( Биг-Омега) нотация (статья) | Ханская академия

  • Резюме
    «Большой O» описывает производительность алгоритма и оценивает его.

    или обратиться к нему формально, «Big O» классифицирует алгоритмы и стандартизирует процесс сравнения.

7
2018-04-13 13: 53: 42Z

Самый простой способ взглянуть на него (простым языком)

Мы пытаемся увидеть, как количество входных параметров влияет на время работы алгоритма. Если время выполнения вашего приложения пропорционально количеству входных параметров, то оно называется Big O of n.

Вышеприведенное утверждение - хорошее начало, но не совсем верно.

Более точное объяснение (математическое)

Предположим, что

n = количество входных параметров

T (n) = Фактическая функция, которая выражает время работы алгоритма как функцию от n

c = константа

f (n) = приблизительная функция, которая выражает время работы алгоритма как функцию от n

Тогда, что касается Big O, аппроксимация f (n) считается достаточно хорошей, если выполняется условие, приведенное ниже.

 
lim     T(n) ≤ c×f(n)
n→∞

Уравнение читается как Когда n приближается к бесконечности, T of n меньше или равно c раз f от n.

В большой записи O это пишется как

 
T(n)∈O(n)

Это читается как T из n в большом O из n.

Назад на английский

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

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

Проверьте это видео учебник по Big O от Калифорнийского университета в Беркли. На самом деле это простая концепция. Если вы услышите, как профессор Шевчук (он же учитель уровня Бога) объясняет это, вы скажете: «О, вот и все!».

    
6
2016-09-15 14: 15: 12Z

Я нашел действительно отличное объяснениео большой нотации, особенно для тех, кто не очень любит математику.

https: //rob- bell.net/2009/06/a-beginners-guide-to-big-o-notation/ р>

  

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

     

Любой, кто читал «Программирование жемчуга» или любую другую информатику   книги и не имеет оснований по математике ударит в стену   когда они достигли глав, в которых упоминается O (N log N) или другие, казалось бы,   сумасшедший синтаксис. Надеюсь, эта статья поможет вам получить   понимание основ большого О и логарифмов.

     

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

     

О (1)

     

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

 
bool IsFirstElementNull(IList<string> elements) {
    return elements[0] == null; } O(N)
     

O (N)

     

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

 
bool ContainsValue(IList<string> elements, string value) {
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
} 
     

O (N 2 )

     

O (N 2 ) представляет алгоритм, производительность которого напрямую   пропорционально квадрату размера входного набора данных. Это   общий с алгоритмами, которые включают вложенные итерации по данным   задавать. Более глубокие вложенные итерации приведут к O (N 3 ), O (N 4 ) и т. Д.

 
bool ContainsDuplicates(IList<string> elements) {
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}
     

О (2 N )

     

O (2 N ) обозначает алгоритм, рост которого удваивается с каждым дополнением к   набор входных данных. Кривая роста функции O (2 N )   экспоненциальный - начиная с очень мелкого, затем поднимаясь метеорически.   Примером функции O (2 N ) является рекурсивное вычисление Фибоначчи   Номера:

 
int Fibonacci(int number) {
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}
     

Логарифмы

     

Логарифмы немного сложнее объяснить, поэтому я буду использовать общий   Пример: р>      

Бинарный поиск - это метод, используемый для поиска в отсортированных наборах данных. Оно работает   выбрав средний элемент набора данных, по существу   медиана, и сравнивает его с целевым значением. Если значения соответствуют ему   вернет успех. Если целевое значение выше, чем значение   элемент зонда это займет верхнюю половину набора данных и   выполнить ту же операцию против него. Аналогично, если целевое значение   ниже, чем значение элемента зонда, он будет выполнять   операция против нижней половины. Это будет продолжать вдвое данных   установить для каждой итерации, пока значение не будет найдено или пока оно не может   больше не разбивать набор данных.

     

Этот тип алгоритма описывается как O (log N). Итеративное деление пополам   наборов данных, описанных в примере двоичного поиска, приводит к росту   кривая, которая достигает пика в начале и медленно выравнивается как размер   наборов данных увеличивается, например, набор входных данных, содержащий 10 элементов   занимает одну секунду, набор данных, содержащий 100 элементов занимает   две секунды, и набор данных, содержащий 1000 элементов, займет три   секунд. Удвоение размера набора входных данных мало влияет на   его рост как после одной итерации алгоритма набора данных   будет уменьшен вдвое и, следовательно, наравне с входным набором данных   размер. Это делает алгоритмы, такие как бинарный поиск, чрезвычайно эффективными   при работе с большими наборами данных.

    
5
2018-10-31 17: 47: 18Z

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

Допустим, ваш алгоритм решения проблемы зависит от некоторых «факторов», например, давайте сделаем это N и X.

В зависимости от N и X вашему алгоритму потребуются некоторые операции, например, в худшем случае это 3(N^2) + log(X) операций.

SinBig-O не слишком заботится о постоянном множителе (он же 3), Big-O вашего алгоритма - O(N^2 + log(X)). Это в основном переводит «количество операций, необходимое вашему алгоритму для наихудшего случая, масштабируемого этим».

    
4
2015-10-11 18: 00: 20Z

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

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

Я бы посоветовал вам посмотреть это видео на YouTube, которое объясняет примечание Big O в глубина с примерами кода.

 Основные принципы алгоритма

Так, например, предположим, что алгоритм занимает 5 записей, а время, необходимое для его обработки, составляет 27 секунд. Теперь, если мы увеличим количество записей до 10, алгоритм займет 105 секунд.

Простыми словами, занимаемое время является квадратом количества записей. Мы можем обозначить это как O (n ^ 2) . Это символическое представление называется обозначением Big O.

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

 Большие символы O

Например, посмотрите на приведенную ниже функцию «Function1», которая принимает коллекцию и выполняет обработку первой записи. Теперь для этой функции производительность будет одинаковой, независимо от того, поставили вы 1000, 10000 или 100000 записей. Таким образом, мы можем обозначить его как O (1) .

 
void Function1(List<string> data)
{
string str = data[0];
}

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

 
void Function2(List<string> data)
        {
            foreach(string str in data)
            {
                if (str == "shiv")
                {
                    return;
                }
            }
        }

Когда мы видим обозначение Big O для любого алгоритма, мы можем классифицировать его по трем категориям производительности: -

  1. Категория журнала и констант: - Любой разработчик хотел бы увидеть производительность своего алгоритма в этой категории.
  2. Линейный. - Разработчик не захочет видеть алгоритмы в этой категории, пока не останется его последний вариант или единственный параметр.
  3. Экспоненциальный: - здесь мы не хотим видеть наши алгоритмы, и необходима доработка.

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

 Болотная классификация

Я бы порекомендовал вам посмотреть это 10-минутное видео, в котором обсуждается Big O с примером кода.

https://www.youtube.com/watch?v=k6kxtzICG_g р>     

4
2018-05-11 09: 43: 53Z
источник размещен Вот