Big O, как вы рассчитываете / приближаете это?

Question

Большинство людей со степенью в CS наверняка знают, что означает Big O . Это помогает нам измерить, насколько (не) эффективен алгоритм на самом деле, и если вы знаете, в , в какой категории находится проблема, которую вы пытаетесь решить, в , вы можете выяснить, все еще возможно ли выжать этот маленький дополнительная производительность. ¹

Но мне любопытно, как вы рассчитываете или приближаете сложность ваших алгоритмов?

¹ _{но, как говорится, не переусердствуйте, преждевременная оптимизация - корень всего зла , и оптимизация без уважительной причины должна заслужить это имя как хорошо.}

Answer 1

Я сделаю все возможное, чтобы объяснить это здесь простыми терминами, но имейте в виду, что эта тема займет у моих студентов пару месяцев, чтобы наконец понять. Вы можете найти больше информации о главе 2 Структуры данных и алгоритмов в Java book.

---

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

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

Цель проста: сравнить алгоритмы с теоретической точки зрения без необходимости выполнения кода. Чем меньше количество шагов, тем быстрее алгоритм.

Например, предположим, у вас есть этот кусок кода:

int sum(int* data, int N) {
    int result = 0;               // 1

    for (int i = 0; i < N; i++) { // 2
        result += data[i];        // 3
    }

    return result;                // 4
}

Эта функция возвращает сумму всех элементов массива, и мы хотим создать формулу для подсчета сложности вычислений этой функции:

Number_Of_Steps = f(N)

Итак, у нас есть f(N), функция для подсчета количества вычислительных шагов. Ввод функции - это размер обрабатываемой структуры. Это означает, что эта функция называется так:

Number_Of_Steps = f(data.length)

Параметр N принимает значение data.length. Теперь нам нужно актуальное определение функции f(). Это делается из исходного кода, в котором каждая интересующая строка пронумерована от 1 до 4.

Есть много способов вычислить BigOh. С этого момента мы будем предполагать, что каждое предложение, которое не зависит от размера входных данных, принимает постоянное C число вычислительных шагов.

Мы собираемся добавить индивидуальное количество шагов функции, и ни объявление локальной переменной, ни инструкция возврата не зависят от размера массива data.

Это означает, что в строках 1 и 4 выполняется C количество шагов каждая, и функция выглядит примерно так:

f(N) = C + ??? + C

Следующая часть должна определить значение оператора for. Помните, что мы рассчитываем количество вычислительных шагов, то есть тело оператора for выполняется N раз. Это то же самое, что добавить C, N раз:

f(N) = C + (C + C + ... + C) + C = C + N * C + C

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

Чтобы получить фактическое значение BigOh, нам понадобится Асимптотический анализ функции. Это примерно так:

1. Уберите все константы C.
2. Из f() получите полином в его standard form.
3. Разделите члены полиномиума и отсортируйте их по скорости роста.
4. Держите тот, который увеличивается, когда N приближается к infinity.

Наше f() имеет два термина:

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

Удаление всех C констант и избыточных частей:

f(N) = 1 + N ^ 1

Так как последний член становится тем, который увеличивается, когда f() приближается к бесконечности (подумайте о limit ), это аргумент BigOh, а функция sum() имеет BigOh:

O(N)

---

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

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

for (i = 0; i < 2*n; i += 2) {  // 1
    for (j=n; j > i; j--) {     // 2
        foo();                  // 3
    }
}

Первое, что вам нужно было спросить, это порядок исполнения foo(). Хотя обычно это O(1), вы должны спросить об этом своих профессоров. O(1) означает (почти, в основном) постоянную C, не зависящую от размера N.

Утверждение for в предложении номер один сложно. Пока индекс заканчивается на 2 * N, приращение делается на два. Это означает, что первые for выполняются только N шагов, и нам нужно разделить счет на два.

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

Номер предложения two еще сложнее, поскольку зависит от значения i. Посмотрите: индекс i принимает значения: 0, 2, 4, 6, 8, ..., 2 * N, а второй for выполняется: N раз первый, N - 2 второй, N - 4 третий ... до этапа N / 2, на котором второй for никогда не выполняется.

По формуле это означает:

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

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

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

(Мы предполагаем, что foo() равно O(1) и делает C шагов.)

У нас здесь проблема: когда i принимает значение N / 2 + 1 вверх, внутреннее суммирование заканчивается отрицательным числом! Это невозможно и неправильно. Нам нужно разделить суммирование на две части, являясь поворотной точкой в ​​момент, когда i занимает N / 2 + 1.

.

f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )

С момента поворота i > N / 2 внутренний for не будет выполнен, и мы предполагаем постоянную сложность выполнения C в его теле.

Теперь суммирование можно упростить с помощью некоторых правил идентификации:

1. Суммирование (ш от 1 до N) (C) = N * C
2. Суммирование (w от 1 до N) (A (+/-) B) = Суммирование (w от 1 до N) (A) (+/-) Суммирование (w от 1 до N) (B)
3. Суммирование (w от 1 до N) (w * C) = C * Суммирование (w от 1 до N) (w) (C является константой, независимой от w)
4. Суммирование (w от 1 до N) (w) = (N * (N + 1)) / 2

Применение некоторой алгебры:

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )

f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )

=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )

=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = 

   (N / 2 - 1) * (N / 2) / 2 = 

   ((N ^ 2 / 4) - (N / 2)) / 2 = 

   (N ^ 2 / 8) - (N / 4)

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )

f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + C * N

f(N) = C * 1/4 * N ^ 2 + C * N

И BigOh это:

O(N²)

Answer 2

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

Несколько примеров того, как это используется в коде C.

Скажем, у нас есть массив из n элементов

int array[n];

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

x = array[0];

Если мы хотим найти номер в списке:

for(int i = 0; i < n; i++){
    if(array[i] == numToFind){ return i; }
}

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

Когда мы доберемся до вложенных циклов:

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        array[j] += 2;
    }
}

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

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

Answer 3

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

Вот некоторые из наиболее распространенных случаев, снятых с http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions:

O (1) - определение, является ли число четным или нечетным; использование таблицы поиска постоянного размера или хэш-таблицы

O (logn) - Поиск элемента в отсортированном массиве с помощью двоичного поиска

O (n) - поиск элемента в несортированном списке; добавление двух n-значных чисел

O (n ² ) - умножение двух n-значных чисел простым алгоритмом; добавление двух n × n матриц; пузырьковая сортировка или вставка сортировки

O (n ³ ) - Умножение двух матриц n × n простым алгоритмом

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

O (n!) - решение проблемы коммивояжера с помощью поиска методом перебора

O (n ⁿ ) - Часто используется вместо O (n!) Для получения более простых формул для асимптотической сложности

Answer 4

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

Это означает, что между алгоритмом в O (n) и алгоритмом в O (n ² ) самый быстрый не всегда является первым (хотя всегда существует значение n такое, что для задач размером> n, первый алгоритм самый быстрый).

Обратите внимание, что скрытая константа очень сильно зависит от реализации!

Кроме того, в некоторых случаях время выполнения не является детерминированной функцией размера n входных данных. Возьмем, к примеру, сортировку с использованием быстрой сортировки: время, необходимое для сортировки массива из n элементов, не является константой, а зависит от начальной конфигурации массива.

Существуют различные временные сложности:

• Худший случай (обычно самый простой, но не всегда очень значимый)

• Средний случай (обычно гораздо сложнее выяснить ...)

• ...

Хорошим введением является Введение в анализ алгоритмов Р. Седжвика и П. Флайолета.

Как вы говорите, premature optimisation is the root of all evil и (если возможно) profiling действительно всегда должны использоваться при оптимизации кода. Это может даже помочь вам определить сложность ваших алгоритмов.

Answer 5

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

Также я хотел бы добавить, как это делается для рекурсивных функций :

предположим, что у нас есть такая функция ( код схемы ):

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))

, который рекурсивно вычисляет факториал данного числа.

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

Итак, производительность для тела: O (1) (постоянная).

Затем попытайтесь определить это для количества рекурсивных вызовов . В этом случае у нас n-1 рекурсивных вызовов.

Таким образом, производительность для рекурсивных вызовов: O (n-1) (порядок равен n, поскольку мы отбрасываем незначительные части).

Затем соедините эти два, и вы получите производительность для всей рекурсивной функции:

1 * (n-1) = O (n)

---

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

Answer 6

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

O ((n / 2 + 1) * (n / 2)) = O (n ² / 4 + n / 2) = O (n ² / 4 ) = O (n ² )

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

O (log N ) N ) N log N ) N ² ) N ^k ) n ) п !)

Answer 7

Я думаю об этом с точки зрения информации. Любая проблема состоит в изучении определенного количества битов.

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

Например, оператор if, имеющий две ветви, одинаково вероятные, имеет энтропию 1/2 * log (2/1) + 1/2 * log (2/1) = 1/2 * 1 + 1/2 * 1 = 1. Таким образом, его энтропия составляет 1 бит.

Предположим, вы ищете таблицу из N элементов, например, N = 1024. Это 10-битная проблема, потому что log (1024) = 10 бит. Поэтому, если вы можете искать его с помощью утверждений IF, которые имеют одинаково вероятные результаты, необходимо принять 10 решений.

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

Предположим, вы выполняете линейный поиск. Вы смотрите на первый элемент и спрашиваете, хотите ли вы. Вероятности составляют 1/1024, а 1023/1024 - нет. Энтропия этого решения составляет 1/1024 * log (1024/1) + 1023/1024 * log (1024/1023) = 1/1024 * 10 + 1023/1024 * около 0 = около 0,01 бита. Вы узнали очень мало! Второе решение не намного лучше. Вот почему линейный поиск такой медленный. На самом деле это экспоненциальное число битов, которые вам нужно выучить.

Предположим, вы занимаетесь индексацией. Предположим, что таблица предварительно отсортирована по множеству бинов, и вы используете некоторые из всех битов в ключе для индексации непосредственно к записи таблицы. При наличии 1024 бинов энтропия составляет 1/1024 * log (1024) + 1/1024 * log (1024) + ... для всех 1024 возможных результатов. Это 1/1024 * 10 × 1024 результатов или 10 битов энтропии для этой одной операции индексации. Вот почему поиск по индексу выполняется быстро.

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

Таким образом, сортировки, основанные на бинарных решениях, имеющих примерно одинаково вероятные результаты, все принимают за O (N log N) шагов. Алгоритм сортировки O (N) возможен, если он основан на поиске по индексу.

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

Answer 8

Давайте начнем с начала.

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

1. Арифметические операции (например, + или%).
2. Логические операции (например, &&).
3. Операции сравнения (например, <=). </li>
4. Операции доступа к структуре (например, индексирование массива, например, A [i], или указатель с оператором ->).
5. Простое присвоение, например, копирование значения в переменную.
6. Вызов функций библиотеки (например, scanf, printf).

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

1. Операторы присваивания, которые не включают вызовы функций в своих выражениях.
2. Читать заявления.
3. Написать операторы, которые не требуют вызовов функций для оценки аргументов.
4. Операторы перехода ломают, продолжают, переходят и возвращают выражение, где выражение не содержит вызов функции.

В C многие циклы for формируются путем инициализации переменной индекса некоторым значением и увеличивая эту переменную на 1 каждый раз вокруг цикла. Цикл for заканчивается, когда индекс достигает некоторого предела. Например, цикл for

for (i = 0; i < n-1; i++) 
{
    small = i;
    for (j = i+1; j < n; j++)
        if (A[j] < A[small])
            small = j;
    temp = A[small];
    A[small] = A[i];
    A[i] = temp;
}

использует индексную переменную i. Увеличивает i на 1 каждый раз вокруг цикла и итераций остановитесь, когда я достигну n - 1.

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

Например, цикл for повторяется ((n − 1) − 0)/1 = n − 1 times, поскольку 0 является начальным значением i, n - 1 является наибольшим значением, достигаемым i (то есть, когда i достигает n − 1, цикл останавливается, итераций с i = n − 1 не происходит, и добавляется 1 чтобы я на каждой итерации цикла.

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

---

Теперь рассмотрим этот пример:

(1) for (j = 0; j < n; j++)
(2)   A[i][j] = 0;

Мы знаем, что строка (1) занимает O(1) время. Ясно, что мы обходим цикл n раз, так как мы можем определить, вычитая нижний предел из верхнего предела, найденного в строке (1) и затем добавление 1. Так как тело, строка (2), занимает O (1) время, мы можем пренебречь время для увеличения j и время для сравнения j с n, оба из которых также являются O (1). Таким образом, время выполнения строк (1) и (2) является произведением n и O (1) , что составляет O(n).

Точно так же мы можем ограничить время выполнения внешнего цикла, состоящего из строк (2) - (4), что составляет

(2) for (i = 0; i < n; i++)
(3)     for (j = 0; j < n; j++)
(4)         A[i][j] = 0;

Мы уже установили, что цикл линий (3) и (4) занимает O (n) времени. Таким образом, мы можем пренебречь временем O (1), чтобы увеличить i и проверить, является ли i

Инициализация i = 0 внешнего цикла и (n + 1) -й тест условия Я также беру O (1) время и им можно пренебречь. Наконец, мы видим, что мы идем вокруг внешнего цикла n раз, принимая O (n) время для каждой итерации, давая общее O(n^2) время работы.

---

Более практичный пример.

Answer 9

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

Это имеет несколько преимуществ по сравнению с простым изучением кода. Во-первых, вы можете увидеть, находитесь ли вы в диапазоне, где время выполнения приближается к асимптотическому порядку. Кроме того, вы можете обнаружить, что некоторый код, который, по вашему мнению, был порядка O (x), действительно является порядком O (x ^ 2), например, из-за времени, потраченного на библиотечные вызовы.

Answer 10

В основном, вещь, которая возникает в 90% случаев, это просто анализ циклов. У вас есть одинарные, двойные, тройные вложенные циклы? У вас есть O (n), O (n ^ 2), O (n ^ 3) время работы.

Очень редко (если вы не пишете платформу с обширной базовой библиотекой (например, .NET BCL или C ++ STL), вы сталкиваетесь с чем-то более сложным, чем просто просмотр ваших циклов (для операторов, в то время как , goto и т.д ...)