Где найти значения O (n ^ 2) и O (n) и т. Д.?
I ' мы замечали ответы о переполнении стека, в которых используются подобные термины, но я не знаю, что они означают. Как они называются, и есть ли хороший ресурс, который может объяснить их простыми словами?
4 ответа
Эта нотация называется нотацией Big O , и используется как сокращение для выражения алгоритмической сложности (в основном, сколько времени потребуется для выполнения данного алгоритма при увеличении размера входных данных (n))
Вообще говоря, вы столкнетесь со следующими основными типами алгоритмы:
- O (1) - Константа - Продолжительность времени, необходимого для выполнения этого алгоритма, не зависит от количества элементов, которые алгоритм должен обработать.
- O (log n) - Логарифмический - Продолжительность выполнения этого алгоритма зависит от количества элементов, которые алгоритм должен обработать. По мере увеличения размера ввода для каждого нового ввода требуется меньше времени.
- O (n) - Линейный - Продолжительность выполнения этого алгоритма напрямую зависит от количества элементов, которые алгоритм должен обработать. По мере увеличения размера ввода время, которое требуется, увеличивается в равной степени.
- O (n ^ 2) - Полиномиальный - По мере увеличения размера ввода время, необходимое для обработки ввода, увеличивается на все большую и большую величину - это означает, что большие размеры ввода становятся недопустимо трудными для решения.
- O (2 ^ n) - Экспоненциальная - Самые сложные типы задач. Время обработки увеличивается в зависимости от размера входных данных до крайней степени.
Обычно вы можете приблизительно оценить сложность алгоритма, посмотрев, как он используется.Например, рассмотрим следующий метод:
function sum(int[] x) {
int sum = 0;
for (int i = 0; i < x.length; i++) {
sum += x[i];
}
return sum;
}
Здесь нужно сделать несколько вещей:
- Инициализировать переменную с именем sum
- Инициализировать переменную с именем i
- Для каждой итерации i: добавить x [i] для суммирования, прибавьте 1 к i, проверьте, меньше ли i, чем x.length
- Возврат суммы
Здесь есть несколько операций, которые выполняются с постоянным временем (первые два и последний), поскольку размер of x не повлияет на то, как долго они будут работать. Кроме того, есть некоторые операции, которые выполняются в линейное время (поскольку они выполняются один раз для каждой записи в x). В нотации Big O алгоритм упрощается до наиболее сложных, поэтому этот алгоритм суммирования будет работать в O (n)
Это называется Big O обозначение и используется для количественной оценки сложности алгоритмов.
O (1) означает, что алгоритм требует постоянного времени независимо от того, сколько данных нужно обработать.
O (n) означает, что скорость алгоритма линейно растет с увеличением количества данных.
и так далее ...
Таким образом, чем ниже степень n в нотации O, тем лучше ваш алгоритм решает проблему. В лучшем случае O (1) (n = 0). Но многим задачам присуща сложность, поэтому вы не найдете такой идеальный алгоритм почти во всех случаях.
Пока ответы хорошие. Основной термин для поиска в Интернете - это «нотация Big O».
Основная идея математического выражения «someformula is O (someterm)» заключается в том, что, когда ваша переменная стремится к бесконечности, «someterm» является доминирующей частью формулы.
Например, предположим, что у вас есть 0,05 * x ^ 3 + 300 * x ^ 2 + 200000000 * x + 10 . Для очень малых размеров x (x == 1 или x == 2), это 200000000 * x будет намного большей частью. В этот момент график формулы будет выглядеть линейным. По мере продвижения в какой-то момент часть 300 * x ^ 2 будет больше. Однако, если вы продолжите увеличивать x, сколь угодно большим, часть 0,05 * x ^ 3 будет самой большой и в конечном итоге полностью превзойдет другие части формулы. Вот где из графика становится ясно, что вы смотрите на функцию в кубе. Таким образом, мы бы сказали, что формула O (x ^ 3) .
Сначала прочтите Вычислительную сложность, а затем прочтите несколько книг об алгоритмах, таких как Введение в алгоритмы.
Со страницы Википедии:
Большая нотация O характеризует функции в соответствии с темпами их роста
Если вы не хотите углубляться в детали, очень часто можно приблизительно оценить сложность алгоритма, проанализировав его код:
void simpleFunction(arg); // O(1) - if number of function instructions is constant and don't depend on number of input size
for (int i=0;i<n;i++) {simpleFunction(element[i]);} // O(n)
for (int i=0;i<n;i++) { // this one runs O(n^2)
for (int j=0;j<n;j++) {
simpleFunction(element[i]);
}
}
for (int i=0;i<n;i*=2) { // O(lgn)
simpleFunction(element[i]);
}
Иногда бывает не так просто оценить сложность функции/алгоритма при большой O нотации, в таких случаях используется амортизированный анализ. Приведенный выше код должен служить только в качестве быстрого запуска.