Порядок величины с использованием обозначения Big-O

Question

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

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

count = 0;
for (i = 1; i <= N; i++)
    count++;

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

Answer 1

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

Для большого O, имеющего две функции: f(x) и g (x), где f(x) = O(g(x)), вы можете сказать, что вы можете найти один x, из которого g (x) будет всегда больше чем f (x). Вот почему определение содержит "асимптотически", потому что эти две функции могут иметь любой запуск в начале (например, f (x)> g (x) для нескольких первых x), но из одной точки g (x) будет всегда получать улучшенный (g(x) >= f(x)). Таким образом, вы заинтересованы в поведении в долгосрочной перспективе (не только для небольших чисел). Иногда нотацию big-O называют верхней границей, потому что она описывает наихудший возможный сценарий (асимптотически она никогда не будет более сложной, чем эта функция).

Это "математическая" часть. Когда дело доходит до практики, вы обычно спрашиваете: сколько раз алгоритму придется что-то обрабатывать? Сколько операций будет сделано?

Для вашего простого цикла это легко, потому что по мере того как ваш N будет расти, сложность алгоритма будет расти линейно (как простая линейная функция), поэтому сложность O (N). Для N=10 вам нужно будет выполнить 10 операций, для N=100 => 100 операций, для N=1000 => 1000 операций... Таким образом, рост действительно линейный.

Я приведу еще несколько примеров:

for (int i = 0; i < N; i++) {
   if (i == randomNumber()) {
      // do something...
   }
}

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

Другой пример:

for (int i = 0; i < N; i++) {
   for (int i = 0; i < N; i++) {
       // do something
   }
}

Здесь, поскольку N будет все больше и больше, количество операций будет расти быстрее. Наличие N=10 означает, что вам придется выполнять операции 10x10, операции N=100 => 100x100, операции N=1000 => 1000x1000. Вы можете видеть, что рост уже не линейный, это N x N, поэтому у нас есть O(N x N).

Для последнего примера я буду использовать идею полного бинарного дерева. Надеюсь, вы знаете, что такое двоичное дерево. Итак, если у вас есть простая ссылка на корень, и вы хотите пересечь его к самому левому листу (сверху вниз), сколько операций вам нужно будет выполнить, если в дереве есть N узлов? Алгоритм будет что-то похожее на:

Node actual = root;
while(actual.left != null) {
   actual = actual.left
}
// in actual we have left-most leaf

Сколько операций (как долго будет выполняться цикл) вам придется выполнить? Ну, это зависит от глубины дерева, верно? А как определяется глубина полного бинарного дерева? Это что-то вроде log (N) - с основанием логарифма = 2. Так что здесь сложность будет O(log(N)) - как правило, нас не волнует основание логарифма, нас интересует функция (линейный, квадратичный, логарифмический...)

Answer 2

Ваш пример заказа

НА)

куда N=number of elementsи сопоставимое вычисление выполняется для каждого, таким образом

for (int i=0; i < N; i++) {
    // some process performed N times
}

Нотация big-O, вероятно, проще, чем вы думаете; во всем ежедневном коде вы найдете примеры O(N) в циклах, итерациях списка, поисках и любом другом процессе, который работает один раз для каждого отдельного набора. Это абстракция, которая сначала незнакома, O(N) означает "некоторая единица работы", повторяется N раз. Это "что-то" может быть инкрементным счетчиком, как в вашем примере, или это может быть длительное и ресурсоемкое вычисление. Большую часть времени при разработке алгоритмов "большой-O", или сложность, является более важным, чем единица работы, это особенно актуально, когда N становится большим. Описание "ограничивающий" или "асимптотический" является математически значимым, это означает, что алгоритм меньшей сложности всегда будет превосходить алгоритм, который больше, независимо от того, насколько значительна единица работы, учитывая, что N достаточно велико или "по мере роста N"

Еще один пример, чтобы понять общую идею

for (int i=0; i < N; i++) {
   for (int j=0; j < N; j++) {
    // process here NxN times
   }
}

Здесь сложность

O (N²)

Например, если N=10, то второй "алгоритм" займет в 10 раз больше времени, чем первый, потому что 10x10 = 100 (= в десять раз больше). Если вы подумаете о том, что произойдет, когда N будет равняться, скажем, миллиону или миллиарду, вы сможете понять, что это займет гораздо больше времени. Так что если вы можете найти способ сделать что-то в O(N), как суперкомпьютер в O (N²), вы сможете превзойти его с помощью своего старого x386, карманных часов или другого старого инструмента.