Где найти значения O (n ^ 2), O (n) и т. Д.?

Question

Я замечал ответы о переполнении стека, в которых используются подобные термины, но я не знаю, что они означают.Как они называются, и есть ли хороший ресурс, который может объяснить их простыми словами?

Answer 1

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

Вообще говоря, вы столкнетесь со следующими основными типами алгоритмов:

1. O (1) - Константа - Продолжительность выполнения этого алгоритма не зависит от количества элементов, которые алгоритм должен обработать.
2. O (log n) - Логарифмический - Продолжительность выполнения этого алгоритма зависит от количества элементов, которые алгоритм должен обработать. По мере того как размер ввода увеличивается, для каждого нового ввода требуется меньше времени.
3. O (n) - Линейный - время, которое занимает этот алгоритм, напрямую зависит от количества элементов, которые алгоритм должен обработать. По мере увеличения размера ввода время, которое требуется, увеличивается в равных количествах.
4. O (n ^ 2) - Полиноминальный - По мере увеличения размера ввода время, затрачиваемое на обработку ввода, увеличивается все больше и больше - это означает, что большие размеры ввода становятся непомерно трудными для решения.
5. 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
• Возвращаемая сумма

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

Answer 2

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

Со страницы Википедии:

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

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

Answer 3

Ответы пока хорошие.Основным термином для веб-поиска является «Большая 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).

Answer 4

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

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

O (n) означает, что скорость алгоритма растет линейно с количеством данных.

и т. д. *

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