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

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

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

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

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

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

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

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

• ...

А хорошее введение Введение в Анализ Алгоритмов R. Sedgewick и P. Flajolet.

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

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

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

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

O (logn) - Нахождения объекта в сортированном массиве с двоичным поиском

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

O (n <глоток> 2 ) - Умножение двух N-разрядных чисел простым алгоритмом; добавление двух nГ — n матрицы; пузырьковая сортировка или вид вставки

O (n <глоток> 3 ) - Умножение двух nГ — n матрицы простым алгоритмом

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

O (n!) - Решение проблемы коммивояжера через поиск "в лоб"

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

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

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

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

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

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

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

То, что часто пропускается, , ожидал поведение Ваших алгоритмов. Это не изменяет Большой-O из Вашего алгоритма , но это действительно касается оператора "преждевременная оптимизация...."

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

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

Для реального закрепления его необходимо ли быть в состоянии описать распределение вероятностей "входного пространства" (если необходимо отсортировать список, как часто тот список уже собирается быть отсортированным? как часто это полностью инвертируется? как часто это главным образом отсортировано?) Не всегда выполнимо, что Вы знаете, что, но иногда делаете.

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

, Если Вы действительно хотите ответить на свой вопрос для какого-либо алгоритма лучшее, можно сделать, должен применить теорию. Кроме того, упрощенного "худшего случая" анализ я нашел Амортизируемый анализ очень полезный на практике.

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

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

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

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

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

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

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