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

Question

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

Answer 1

Если я хочу объяснить это 6-летнему ребенку, я начну рисовать некоторые функции f (x) = x и f (x) = x ^ 2, например, и спросить ребенка, какая функция будет верхней функцией на верхняя часть страницы. Затем мы приступим к рисованию и увидим, что x ^ 2 выигрывает. «Кто победит» - это функция, которая растет быстрее, когда x стремится к бесконечности. Таким образом, «функция x в Big O из x ^ 2» означает, что x растет медленнее, чем x ^ 2, когда x стремится к бесконечности. То же самое можно сделать, когда x стремится к 0. Если мы нарисуем эти две функции для x от 0 до 1, то x будет верхней функцией, поэтому «функция x ^ 2 находится в Big O для x для x, стремящегося к 0». Когда ребенок станет старше, я добавляю, что действительно Большой О может быть функцией, которая растет не быстрее, а так же, как данная функция. Более того, константа отбрасывается. Таким образом, 2x в Big O из x.

Answer 2

Введение

алгоритм : процедура / формула для решения проблемы

---

Как анализировать алгоритмы и как мы можем сравнивать алгоритмы друг с другом?

пример: вас и друга просят создать функцию для суммирования чисел от 0 до N. Вы получаете f (x), а ваш друг - g (x). Обе функции имеют одинаковый результат, но разные алгоритмы. Для объективного сравнения эффективности алгоритмов мы используем обозначение Big-O .

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

3 ключевых выноса:

1. Сравнить как быстро растет время выполнения НЕ сравнить точное время выполнения (зависит от аппаратного обеспечения)
2. Относится только к росту времени выполнения относительно ввода (n)
3. Поскольку n становится произвольно большим, сфокусируйтесь на терминах, которые будут расти быстрее всего при увеличении n (думаю, бесконечность). АКА Асимптотический анализ

Сложность пространства: Помимо сложности времени, мы также заботимся о сложности пространства (сколько памяти / пространства использует алгоритм). Вместо проверки времени операций мы проверяем размер выделения памяти.

Answer 3

Big O описывает класс функций.

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

Для данной функции f O (f) описывает все функции g (n), для которых можно найти n0 и постоянную c, так что все значения g (n) при n> = n0 меньше или равны с * е (п)

В менее математических словах O (f) - это набор функций. А именно, все функции, начиная с некоторого значения n0, растут медленнее или быстрее, чем f.

Если f (n) = n, то

g (n) = 3n в O (f). Потому что постоянные факторы не имеют значения h (n) = n + 1000 находится в O (f), потому что оно может быть больше для всех значений меньше 1000, но для больших O имеют значение только огромные входные данные.

Однако i (n) = n ^ 2 отсутствует в O (f), поскольку квадратичная функция растет быстрее, чем линейная.

Answer 4

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

Пример: f (n) = 2 (n ^ 2) + 3n - функция, представляющая время работы гипотетического алгоритма, нотация Big-O по существу дает верхний предел для этой функции, который составляет O (n ^ 2)

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

Также согласен со всеми приведенными выше подробными ответами. Надеюсь, это поможет !!

Answer 5

Большой O на простом английском языке похож на <= (меньше или равно). Когда мы говорим для двух функций f и g, f = O (g), это означает, что f <= g. </p>

Однако это не означает, что для любого n f (n) <= g (n). На самом деле это означает, что <strong>f меньше или равно g с точки зрения роста . Это означает, что после точки f (n) <= c * g (n), если <strong>c является константой . И после точки означает, что для всех n> = n0, где n0 - другая константа .

Answer 6

Представляет скорость алгоритма в в долгосрочной перспективе .

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

Вы можете спокойно перестать читать здесь.

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

Как насчет всех этих математических логарифмов и полиномов ? Оказывается, что алгоритмы по своей природе связаны с этими математическими терминами. Если вы измеряете рост всех детей на блоке, вам потребуется столько же времени, сколько и детей. Это неразрывно связано с понятием n ^ 1 или просто n , где n - не более, чем число детей в блоке. В случае с ультрамарафоном вы измеряете высоту всех детей в вашем городе, но затем вы должны игнорировать время в пути и предполагать, что все они доступны вам в строке (в противном случае мы опережаем текущее объяснение).

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

Но если вы составляете список высот всех детей в вашем городе или, еще лучше, в вашей стране, то вы обнаружите, что то, как вы это делаете, неразрывно связано с математическим log и п ^ 2 . Просматривая свой список, чтобы найти самого маленького ребенка, записать его имя в отдельную тетрадь и вычеркнуть его из оригинальной тетради по сути привязано к математическому n ^ 2 . Если вы подумаете о том, чтобы расположить половину своей записной книжки, а затем другую половину, а затем объединить результаты, вы получите метод, который по сути связан с логарифмом .

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

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

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

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

Answer 7

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

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

Так что, если размер ввода НЕ слишком велик, идея «Большой O» нотации (верхняя граница) будет неважна.

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

int sumArray (int[] nums){
    int sum=0;   // taking initialization and assignments n=1
    for(int i=0;nums.length;i++){
        sum += nums[i]; // taking initialization and assignments n=1
    }
    return sum;
}

В приведенном выше алгоритме, скажем, вы узнаете T(n) следующим образом (сложность по времени):

T(n) = 2*n + 2

Чтобы найти нотацию «Big O», нам нужно рассмотреть очень большой размер ввода:

n= 1,000,000   -> T(1,000,000) = 2,000,002
n=1,000,000,000  -> T(1,000,000,000) = 2,000,000,002
n=10,000,000,000  -> T(10,000,000,000) = 20,000,000,002

Позволяет дать этот аналогичный вход для другой функции F(n) = n

n= 1,000,000   -> F(1,000,000) = 1,000,000 
n=1,000,000,000  -> F(1,000,000,000) = 1,000,000,000
n=10,000,000,000  -> F(10,000,000,000) = 10,000,000,000

Как видно из рисунка, размер входного файла становится слишком большим T(n), приблизительно равным или приближающимся к F(n), поэтому константа 2 и коэффициент 2 становятся слишком незначительными Теперь пришла идея обозначения Big O

O(T(n)) = F(n)
O(T(n)) = n

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

Answer 8

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

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

Можно вычислить Big O, глядя на самые сложные строки алгоритма.

С небольшими или несортированными наборами данных Big O может удивить, так как n log n алгоритмов сложности, таких как двоичный поиск, могут быть медленными для небольших или несортированных наборов, для простого работающего примера линейного поиска по сравнению с бинарным поиском, посмотрите на мой JavaScript пример:

https://codepen.io/serdarsenay/pen/XELWqN?editors=1011 (алгоритмы написаны ниже)

function lineerSearch() {
  init();
  var t = timer('lineerSearch benchmark');
  var input = this.event.target.value;
  for(var i = 0;i<unsortedhaystack.length - 1;i++) {
    if (unsortedhaystack[i] === input) {
      document.getElementById('result').innerHTML = 'result is... "' + unsortedhaystack[i] + '", on index: ' + i + ' of the unsorted array. Found' + ' within ' + i + ' iterations';
      console.log(document.getElementById('result').innerHTML);
      t.stop(); 
      return unsortedhaystack[i]; 
    }
  }
}

function binarySearch () {
  init();
  sortHaystack();
  var t = timer('binarySearch benchmark');
  var firstIndex = 0;
  var lastIndex = haystack.length-1;
  var input = this.event.target.value;

  //currently point in the half of the array
  var currentIndex = (haystack.length-1)/2 | 0;
  var iterations = 0;

  while (firstIndex <= lastIndex) {
    currentIndex = (firstIndex + lastIndex)/2 | 0;
    iterations++;
    if (haystack[currentIndex]  < input) {
      firstIndex = currentIndex + 1;
      //console.log(currentIndex + " added, fI:"+firstIndex+", lI: "+lastIndex);
    } else if (haystack[currentIndex] > input) {
      lastIndex = currentIndex - 1;
      //console.log(currentIndex + " substracted, fI:"+firstIndex+", lI: "+lastIndex);
    } else {
      document.getElementById('result').innerHTML = 'result is... "' + haystack[currentIndex] + '", on index: ' + currentIndex + ' of the sorted array. Found' + ' within ' + iterations + ' iterations';
      console.log(document.getElementById('result').innerHTML);
      t.stop(); 
      return true;
    }
  }
}

Answer 9

Большой О - Экономическая точка зрения.

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

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

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

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

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

Технические примечания. Некоторые примеры временной сложности - O (n) обычно означает, что если проблема имеет размер 'n', я, по крайней мере, должен увидеть все. O (log n) обычно означает, что я делю пополам размер проблемы, проверяю и повторяю, пока задача не будет выполнена. O (n ^ 2) означает, что мне нужно смотреть на пары вещей (например, рукопожатия на вечеринке между n людьми).