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

Question

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

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

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

Answer 1

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

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

Answer 2

Как правило, менее полезно, но для полноты картины есть также Big Omega Ω , который определяет нижнюю границу сложности алгоритма, и Big Theta Θ , которая определяет верхнюю и нижнюю границу.

Answer 3

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

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

Поскольку мы можем найти медиану за время O (n) и разделить массив на две части за время O (n), работа, выполняемая на каждом узле, - это O (k), где k - это размер массива. Каждый уровень дерева содержит (самое большее) весь массив, поэтому работа на уровень составляет O (n) (размеры подмассивов складываются в n, и, поскольку у нас есть O (k) на уровень, мы можем сложить это) , В дереве есть только уровни log (n), так как каждый раз мы вдвое сокращаем ввод.

Таким образом, мы можем ограничить объем работы O (n * log (n)).

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

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

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

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

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

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

Answer 4

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

Answer 5

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

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

Answer 6

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

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

Answer 7

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

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

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

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);

Answer 8

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

Отказ от ответственности: этот ответ содержит ложные утверждения, см. Комментарии ниже.

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

Посетите этот сайт, чтобы получить прекрасное формальное определение Big O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f (n) = O (g (n)) означает, что существуют положительные постоянные c и k, такие что 0 ≤ f (n) ≤ cg (n) для всех n ≥ k. Значения c и k должны быть фиксированы для функции f и не должны зависеть от n.

---

Хорошо, теперь, что мы подразумеваем под сложностями "лучший случай" и "худший случай"?

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

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

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

Answer 9

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

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

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

Answer 10

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

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

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

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