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

Question

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

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

Хорошее:

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

Плохое:

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

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

• O(k^n) Экспоненциальная Время выполнения программы очень быстро увеличивается даже при умеренном увеличении размера задачи - практично обрабатывать небольшие наборы данных с помощью экспоненциальных алгоритмов.
• O(n!) Факториал Время выполнения программы будет больше, чем вы можете позволить себе ожидать чего угодно, кроме самых маленьких и самых банальных наборов данных.

Answer 3

Простой прямой ответ может быть:

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

Answer 4

Хорошо, мои 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} ==> problem-instance-size = 3, итерации в цикле = 3

проблема-экземпляр = {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} ==> problem-instance-size = 3, всего итераций = 3 * 3 = 9

problem-instance = {5,10,15,20,25} ==> problem-instance-size = 5, всего итераций = 5 * 5 = 25

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

Answer 5

Обозначение 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> k, где c и k - некоторые постоянные.

Answer 6

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

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

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

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

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

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

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

Answer 7

Пример алгоритма (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, которая представляет сложность Best-Case:

• Best-Case: ключ - это первая вещь.

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

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

Answer 8

Большой O

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

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

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

Другими словами, на простом английском языке: 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 переходит к.

Примеры

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

• sin x = O (1) при x → + ∞,

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

• x ² + x = O (x ² ) при 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 ² ), когда n → + ∞ (но не наоборот, равенство «фальшивое»),

• O (n) + O (n ² ) = O (n ² ) при n → + ∞

• O (O (n ² )) = O (n ² ) при n → + ∞

• O (n ² ) O (n ³ ) = O (n ⁵ ) при n → + ∞

---

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

Answer 9

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

Answer 10

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

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