Помогите понять Big O

Question

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

Answer 1

Единственная путаница в том, что то, что вы можете считать O (2n), то, что выполняет две операции для каждого элемента в списке, и то, что вы думаете, что O (n), на самом деле оба считаются O ( п)

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

O (2n) = 2 000 000

O (n) = 1 000 000

O (n ^ 2) = 1 000 000 000 000

O (2n) всего в 2 раза медленнее, чем O (n), но O (n ^ 2) в миллион раз медленнее. Это невероятно огромная разница! Таким образом, обозначение Big O на самом деле имеет дело с тем, как алгоритм «масштабирует» или, другими словами, насколько хорошо он работает, когда вы рассматриваете все большие и большие наборы данных.

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

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

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

Answer 2

Что касается объяснений, ребята из StackOverflow, похоже, получают удовольствие от моего примера телефонной книги . Вам также могут понравиться Big O для восьмилетних .

Answer 3

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

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

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

Алгоритмы вычисления n-го элемента последовательности Фибоначчи очень полезны для целей обозначений Big O. Рассмотрим рекурсивный метод решения n-го элемента последовательности Фибоначчи:

fib(n) {
   if (n == 0) 
     return 0;
   else if (n == 1)
     return 1;
   else 
     return fib(n-1) + fib(n-2);
 }

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

Другая реализация Фибоначчи может значительно ускорить алгоритм.

fib(n) {
  fibArr[n + 1];
  fibArr[0] = 0;
  fibArr[1] = 1;


  for(int i = 2; i <= n; i++) {
     fibArr[i] = fibArr[i-1] + fibArr[i-2];
  }
 return fibArr[n];
}

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

Size  -  Linear  -  Exponential
1        1          2
10       10         1024
100      100        1.2676506e+30
1000     1000       1.071509e+301

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

Существует еще многое для анализа Big O. Рассмотрим эти различные типы классификаций для Big O.

Constant time - O(1)
Logarithmic - O(logn)
Linear - O(n)
Quadratic - O(n^2)
Exponential - O(2 ^n)
Factorial - O(n!)

При выборе алгоритма важно понимать приблизительное время работы и пространство, необходимое для выполнения алгоритма.