Big O, как вы вычислить / округлить?

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

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

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

int array[n];

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

x = array[0];

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

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

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

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

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

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

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

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

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

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

O (LOGN) - Нахождение элемента в отсортированном массиве с бинарным поиском

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

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

О (п ³ ) - Умножение два N × N матриц с помощью простого алгоритма

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

O (N!) - Решение задачи коммивояжера с помощью поиска перебора

О (п ^п ) - часто используется вместо O (N!) , Чтобы получить более простые формулы для асимптотической сложности

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

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

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

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

Есть разные сложности времени:

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

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

• ...

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

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

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

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

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

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

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

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

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

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

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

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

1 * (п-1) = О (п)

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

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

O ((N / 2 + 1) * (п / 2)) = О (п ² /4 + п / 2) = О (п ² /4) = О (п ² )

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

O (журнал N ) <O ( N ) <O ( N журнал N ) <O ( N ² ) <О ( Н ^к ) <О (е ^п ) <О ( п !)

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

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

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

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

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

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

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

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

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

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

Начнем с самого начала.

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

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

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

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

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

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

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

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

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

Теперь рассмотрим следующий пример:

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

Мы знаем , что линия (1) занимает O(1)время. Ясно, что идет вокруг петли п раз, как мы можем определить путем вычитания нижнего предела от верхнего предела найденного на линии (1) , а затем добавление 1. Так как тела, линия (2), занимает O (1) время, мы можем пренебречь время , чтобы увеличить J и время , чтобы сравнить с п J, оба из которых также является O (1). Таким образом, время работы линий (1) и (2) является произведением п и 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 и испытать <ли я п в каждой итерации, заключив, что каждая итерация внешнего цикла занимает O (N) времени.

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

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

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

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

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

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

Менее полезен в целом, я думаю, но для полноты картины есть также большой Omega Ом , которая определяет нижайший переплете по сложности алгоритма , в, и большая Тета & thetas , который определяет , как верхний и нижний предел.

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

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

Так как мы можем найти медиану в O (N) времени и разделить массив на две части в O (N) времени, работа осуществляется в каждом узле представляет собой О (к), где к является размер массива. Каждый уровень дерева содержит (в большинстве) весь массив поэтому работа на уровне O (п) (размеры подмассивов добавить до п, а так как мы имеем O (K) на уровне, мы можем добавить это вверх) , Есть только журнал (п) уровней в дереве, так как каждый раз, когда мы вдвое вход.

Поэтому мы можем верхней границы объема работ на О (п * журнала (п)).

Тем не менее, Big O скрывает некоторые детали, которые мы иногда не можем игнорировать. Рассмотрим вычисления последовательности Фибоначчи с

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

и позволяет только предполагать а и Ь BigIntegers в Java или что-то, что может обрабатывать сколь угодно большие числа. Большинство людей скажут, что это (п) алгоритм O без содрогания. Полагают, что у вас есть п итераций в цикл и O (1) работа в стороне цикла.

Но числа Фибоначчи велики, п-е число Фибоначчи экспоненту в п так просто хранить это займет порядка п байт. Выполнение сложения с большими целыми числами будет принимать O (N) объем работы. Таким образом, общий объем работы, проделанный в этой процедуре

1 + 2 + 3 + ... + п = п (п-1) / 2 = O (N ^ 2)

Так что этот алгоритм работает в quadradic время!

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

Для получения дополнительной информации, проверьте страницу Википедии на эту тему.

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

За 1 - й случай, внутренний цикл выполняется n-iраз, так что общее число казней является суммой для iперехода от 0к n-1(потому что ниже, не ниже , чем или равно) из n-i. Вы наконец -то n*(n + 1) / 2, так O(n²/2) = O(n²).

Для 2 - го цикла, iмежду 0и nвключены для внешнего контура; то внутренний цикл выполняется , когда jстрого больше n, которое затем невозможно.

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

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

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

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

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

int nCmp = 0;
System.Random rnd = new System.Random();

// measure the time required to sort a list of n integers
void DoTest(int n)
{
   List<int> lst = new List<int>(n);
   for( int i=0; i<n; i++ )
      lst[i] = rnd.Next(0,1000);

   // as we sort, keep track of the number of comparisons performed!
   nCmp = 0;
   lst.Sort( delegate( int a, int b ) { nCmp++; return (a<b)?-1:((a>b)?1:0)); }

   System.Console.Writeline( "{0},{1}", n, nCmp );
}


// Perform measurement for a variety of sample sizes.
// It would be prudent to check multiple random samples of each size, but this is OK for a quick sanity check
for( int n = 0; n<1000; n++ )
   DoTest(n);

Что часто упускают из виду это ожидаемое поведение ваших алгоритмов. Это не меняет Big-O вашего алгоритма , но это не относится к утверждению «преждевременная оптимизация.. ..»

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

Например, если вы ищете значение в списке, это O (п), но если вы знаете, что большинство списков вы видите есть ваше значение фронта, типичное поведение вашего алгоритма быстрее.

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

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

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

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

Отличный вопрос!

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

Проверьте этот сайт для прекрасного формального определения Big O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

е (п) = О (г (п)) означает, что существуют положительные константы С и К, такие, что 0 ≤ F (N) ≤ CG (п) для всех п ^ к. Значения С и К должны быть установлены для функции F и не должны зависеть от п.

Итак, теперь, что мы понимаем под «лучшим случаем» и «наихудшей» сложности?

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

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

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

Я не знаю, как программно решить эту проблему, но первое, что люди делают то, что мы образец алгоритма для некоторых моделей в число операций делается, скажем, 4n ^ 2 + 2n + 1 мы имеем 2 правила:

1. Если у нас есть сумма членов, срок с наибольшим темпом роста сохраняется, с другими условиями опущены.
   
2. Если у нас есть произведение нескольких факторов постоянные факторы опущены.

Если упростить F (X), где F (X) есть формула для числа операций сделано, (4n ^ 2 + 2n + 1 объяснено выше), получим значение большого-O [O (N ^ 2) в этом дело]. Но это было бы объяснить Лагранж интерполяции в программе, которая может быть трудно реализовать. А что, если реальная стоимость большой-O была O (2 ^ п), и мы могли бы иметь что-то вроде O (х ^ п), так что этот алгоритм, вероятно, не будет программироваться. Но если кто-то доказывает меня неправильно, дайте мне код. , , ,

Для получения кода А, внешний цикл будет выполняться в течение N + 1 раз, «1» означает, что время, процесс, который проверяет, сохраняется ли я удовлетворяет требованию. И внутренняя запускает цикл п раз, п-2 раза .... Таким образом, 0 + 2 + .. + (N-2) + п = (0 + п) (п + 1) / 2 = О (N²).

Для получения кода B, хотя внутренний цикл не будет шаг и выполнить Foo (), внутренний цикл будет выполняться в п раз зависят от времени выполнения внешнего цикла, который представляет собой О (п)