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

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

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

Может быть, вам на самом деле не нужно улучшать сложность вашего алгоритма, но вы должны по крайней мере быть в состоянии вычислить его, чтобы принять решение ...
Xavier Nodet 23.09.2008 20:58:18
Я нашел это очень четкое объяснение Большой О, Большой Омеги и Большой Теты
Sam Dutton 3.12.2010 12:21:51
-1: Вздох, еще одно злоупотребление BigOh. BigOh - это просто асимптотическая верхняя граница, которая может использоваться для чего угодно и не только для CS. Говорить о BigOh как об одном уникальном бессмысленно (линейный алгоритм времени также O (n ^ 2), O (n ^ 3) и т. Д.). Сказать, что это помогает нам измерить эффективность, также вводит в заблуждение. Кроме того, что со ссылкой на классы сложности? Если все, что вас интересует, это методы расчета времени работы алгоритмов, насколько это актуально?
Aryabhatta 23.05.2011 17:35:02
Big-O не измеряет эффективность; он измеряет, насколько хорошо алгоритм масштабируется по размеру (это может относиться и к другим вещам, кроме размера, но это то, что нам, вероятно, здесь интересно) - и это только асимптотически, так что если вам не повезло, алгоритм с «меньшим» большим O может быть медленнее (если Big-O относится к циклам), чем другой, пока вы не достигнете чрезвычайно больших чисел.
ILoveFortran 5.09.2011 17:05:18
Выбор алгоритма на основе его сложности Big-O обычно является важной частью разработки программы. Это, безусловно, не случай «преждевременной оптимизации», которая в любом случае является злоупотреблением выборочной цитатой.
user207421 31.01.2016 23:52:01
23 ОТВЕТА
РЕШЕНИЕ

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


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

Предложение номер два еще сложнее, поскольку оно зависит от значения 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. Суммирование (w от 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²)
1475
5.03.2019 17:54:37
@arthur Это будет O (N ^ 2), потому что вам понадобится один цикл для чтения всех столбцов и один цикл для чтения всех строк определенного столбца.
Abhishek Dey Das 14.11.2014 20:34:47
@arthur: Это зависит. Это O(n)где nколичество элементов, или O(x*y)где xи yразмеры массива. Big-oh "относительно ввода", поэтому зависит от того, что вы вводите.
Mooing Duck 6.04.2015 22:55:57
Отличный ответ, но я действительно застрял. Как Суммирование (я от 1 до N / 2) (N) превращается в (N ^ 2/2)?
Parsa 19.11.2015 11:35:52
@ParsaAkbari Как правило, сумма (i от 1 до a) (b) равна a * b. Это просто еще один способ сказать b + b + ... (a times) + b = a * b (по определению для некоторых определений целочисленного умножения).
Mario Carneiro 24.11.2015 14:26:36
Не очень актуально, но просто чтобы избежать путаницы, в этом предложении есть маленькая ошибка: «индекс i принимает значения: 0, 2, 4, 6, 8, ..., 2 * N». Индекс я на самом деле идет до 2 * N - 2, цикл остановится.
Albert 12.02.2016 13:12:37

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

7
24.05.2011 22:15:58

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

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

7
6.08.2008 11:34:26

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

Несколько примеров того, как это используется в 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 в квадрате.

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

201
6.08.2008 13:34:13
Отличное объяснение! Так что, если кто-то говорит, что его алгоритм имеет сложность O (n ^ 2), значит ли это, что он будет использовать вложенные циклы?
Navaneeth K N 31.07.2009 04:29:52
Не совсем, любой аспект, который приводит к n квадратам времени, будет рассматриваться как n ^ 2
asyncwait 9.10.2009 11:21:42
@NavaneethKN: Вы не всегда будете видеть вложенный цикл, поскольку вызовы функций могут работать> O(1)сами по себе. В стандартных API C, например, bsearchизначально O(log n), strlenесть O(n)и qsortесть O(n log n)(технически это не дает никаких гарантий, а сама быстрая сортировка имеет наихудшую сложность случая O(n²), но если предположить, что ваш libcавтор не дебил, его средняя сложность случая есть, O(n log n)и он использует стратегия выбора разворота, которая уменьшает шансы попадания в O(n²)дело). И как bsearchи qsortможет быть хуже , если функция компаратора патологическая.
ShadowRanger 21.03.2019 14:36:53

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

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

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

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


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

28
23.05.2017 12:10:45
Свен, я не уверен, что твой способ оценки сложности рекурсивной функции сработает для более сложных, таких как поиск / суммирование / что-то сверху вниз в двоичном дереве. Конечно, вы могли бы привести простой пример и придумать ответ. Но я полагаю, что для рекурсивных вычислений вам действительно понадобится математика?
Peteter 15.08.2008 05:46:56
+1 за рекурсию ... Также эта прекрасна: "... даже профессор побуждал нас думать ..." :)
TT_ 19.01.2014 03:09:58
Да, это так хорошо. Я склонен думать так, чем выше термин внутри О (..), тем больше работа, которую вы / машина делаете. Думать об этом, относясь к чему-то, может быть приблизительным, но также и эти границы. Они просто говорят вам, как увеличивается объем работы, когда количество входов увеличивается.
Abhinav Gauniyal 22.04.2015 16:54:33

Обозначение 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)

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

8
8.08.2008 13:53:20
Вам не нужно заботиться о том, как хранятся числа, это не меняет того, что алгоритм растет с верхним пределом O (n).
mikek3332002 23.07.2010 03:40:19

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

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

10
14.08.2008 15:35:50
Зависит от петель.
kelalaka 30.09.2018 22:02:44

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

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

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

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

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

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

  • ...

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

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

43
4.03.2015 12:48:31
В математике O (.) Означает верхнюю границу, а theta (.) Означает, что у вас есть граница сверху и снизу. Является ли определение на самом деле другим в CS, или это просто обычное злоупотребление нотацией? По математическому определению sqrt (n) - это и O (n), и O (n ^ 2), поэтому не всегда бывает, что существует некоторый n, после которого функция O (n) меньше.
Douglas Zare 26.02.2015 13:59:40

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

В качестве очень простого примера скажем, что вы хотели проверить правильность сортировки списка .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);
5
5.09.2008 18:33:32

Хотя знание того, как рассчитать время Big 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!) Для получения более простых формул для асимптотической сложности

95
4.03.2015 12:57:13
Почему бы не использовать x&1==1для проверки на странность?
Samy Bencherif 11.12.2017 06:15:14
@SamyBencherif: Это был бы типичный способ проверки (на самом деле, достаточно x & 1было бы просто проверить, проверять не нужно == 1; в C x&1==1это оценивается как x&(1==1) приоритет оператора , так что фактически это то же самое, что и тестирование x&1). Я думаю, что вы неправильно читаете ответ; там есть точка с запятой, а не запятая. Это не говорит о том, что вам понадобится таблица соответствия для четного / нечетного тестирования, это говорит о том, что как четное / нечетное тестирование, так и проверка таблицы поиска являются O(1)операциями.
ShadowRanger 21.03.2019 14:42:39
Я не знаю о требовании использования в последнем предложении, но кто бы это ни делал, он заменяет класс другим, который не эквивалентен. Класс O (n!) Содержит, но строго больше, чем O (n ^ n). Фактическая эквивалентность будет O (n!) = O (n ^ ne ^ {- n} sqrt (n)).
conditionalMethod 26.09.2019 17:52:28

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

8
24.05.2011 22:21:24

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

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

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

4
14.10.2008 20:16:38

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

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

14
11.12.2008 20:49:05
Просто чтобы обновить этот ответ: en.wikipedia.org/wiki/Analysis_of_algorithms , эта ссылка имеет формулу, которая вам нужна. Многие алгоритмы следуют строгому правилу, если у вас есть, с 2 точками времени и 2 средами исполнения на машине, мы можем вычислить наклон на графике log-log. Это a = log (t2 / t1) / log (n2 / n1), это дало мне показатель степени для алгоритма в, O (N ^ a). Это можно сравнить с ручным расчетом с помощью кода.
Christopher John 28.11.2018 12:43:45
Привет, хороший ответ. Мне было интересно, знаете ли вы какую-либо библиотеку или методологию (например, я работаю с python / R), чтобы обобщить этот эмпирический метод, то есть подобрать подгонку различных функций сложности к увеличивающемуся набору данных и выяснить, какие из них актуальны. Спасибо
agenis 22.01.2019 13:19:30

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

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

Например, 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) возможен, если он основан на поиске по индексу.

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

22
4.03.2015 13:10:19
Вау. У вас есть полезные ссылки на это? Я чувствую, что это полезно для меня, чтобы проектировать / реорганизовывать / отлаживать программы.
Jesvin Jose 11.09.2011 08:43:37
@aitchnyu: Для чего это стоит, я написал книгу на эту и другие темы. Это давно вышло из печати, но копии идут по разумной цене. Я пытался заставить GoogleBooks захватить его, но в настоящее время немного сложно понять, кто обладает авторскими правами.
Mike Dunlavey 11.09.2011 13:47:26

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

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

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

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

4
10.03.2009 14:30:13

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

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

6
10.03.2009 21:57:40

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

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

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

O (log N ) <O ( N ) <O ( N log N ) <O ( N 2 ) <O ( N k ) <O (e n ) <O ( n !)

26
31.01.2011 13:54:58
конечно O (N) <O (NlogN)
jk. 31.01.2011 13:52:40

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

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

6
31.01.2011 14:36:02

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

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

2
16.01.2019 08:32:43

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

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

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

2
11.05.2013 01:32:45

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

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

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

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

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

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

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

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

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

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


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

введите описание изображения здесь

21
2.02.2014 15:43:11
Что если оператор goto содержит вызов функции? Что-то вроде step3: if (M.step == 3) {M = step3 (done, M); } step4: if (M.step == 4) {M = step4 (M); } if (M.step == 5) {M = step5 (M); перейти к шагу 3; } if (M.step == 6) {M = step6 (M); перейти к шагу 4; } return cut_matrix (A, M); как тогда будет рассчитываться сложность? это будет сложение или умножение? учитывая, что шаг 4 равен n ^ 3, а шаг 5 равен n ^ 2.
Taha Tariq 10.03.2018 05:38:46

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

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

Если вы используете 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, которые зависят от размеров массива, и рассуждения, основанные на ваших структурах данных, какой тип ввода приведет к тривиальным случаям, а какой - к получению. в худших случаях.

4
9.04.2019 04:55:46
Это неверно Большой О означает «верхняя граница», а не худший случай.
Samy Bencherif 11.12.2017 06:10:44
Это распространенное заблуждение, что big-O относится к наихудшему случаю. Как O и Ω относятся к худшему и лучшему случаям?
Dukeling 24.12.2017 14:10:44
Это вводит в заблуждение. Big-O означает верхнюю границу для функции f (n). Омега означает нижнюю границу для функции f (n). Это совсем не связано с лучшим или худшим случаем.
Tasneem Haider 2.03.2019 19:01:41
Вы можете использовать Big-O в качестве верхней границы для лучшего или худшего случая, но кроме этого, да, никакого отношения.
Samy Bencherif 2.03.2019 20:21:21

Я хотел бы объяснить Big-O в несколько ином аспекте.

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

ИМХО в формулах big-O лучше не использовать более сложные уравнения (вы можете просто придерживаться приведенных на следующем графике.) Однако вы все равно можете использовать другие более точные формулы (например, 3 ^ n, n ^ 3, .. .) но иногда это может вводить в заблуждение! Так что лучше держать как можно проще.

введите описание изображения здесь

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

1
20.02.2019 10:44:36