Возможный дубликат:
Простое английское объяснение Big O
Много раз, когда речь идет о сложности времени алгоритма, также учитывается память. Я хочу знать, в чем смысл памяти большого размера O (1), большой O (n), большой-O (n * n)?
И как это связано с временной сложностью?
Как сказал xmoex:
o (1) представляет собой использование постоянной памяти. Таким образом, количество ввода несущественно.
o (n) представляет собой использование линейной памяти. Таким образом, больший объем ввода означает линейно большее количество памяти.
o (n * n) представляет собой квадратичное использование памяти. Таким образом, больший объем ввода означает квадратичное количество памяти (в среднем x ^ 2.
Этот показатель сложности памяти в большинстве случаев полностью независим от меры временной сложности. Для компьютерных алгоритмов важно знать, как алгоритм будет управлять обеими этими сложностями, чтобы определить качество алгоритма. Однако оба они должны рассчитываться отдельно. Один может быть более важным, чем другой, в зависимости от ваших случаев использования и обстоятельств для проблемы.
o (1) означает постоянную среднюю память, независимо от размера вашего ввода
o (n) означает, что если у вас есть n элемент, который вы обрабатываете, ваша средняя потребность в памяти растет линейно
o (n * n) означает, что если у вас есть n элементов, которые вы обрабатываете, ваша средняя потребность в памяти будет расти квадратично
есть статья wiki о так называемой большой нотации (также покрывающей немного...)
Я не уверен, если вы имеете в виду big-O или little-O здесь, но я собираюсь ответить в более общем плане.
Это означает то же самое для памяти, что и для времени. Если функция растет в памяти O (1), то она использует постоянный объем памяти независимо от размера ввода. Если функция растет в O (n), она использует линейную сумму, а O (n * n) использует квадратичную сумму.
Сложность в терминах mamory означает, насколько быстро требуется рост размера памяти при росте количества элементов, подлежащих обработке. Хорошим примером является алгоритм сортировки.
O(1) и O(log n) означают, что при сортировке алгоритма N элементов требуется меньше памяти, а общая память выделяется для N элементов. (Сортировка на месте AKA)O(n) - потребление памяти линейно, поэтому рост потребления памяти при условии роста количества элементов.O(n*n) означает, что для этого алгоритма требуется гораздо больше дополнительной памяти.Здесь каждый объяснил значение нотации Big O. Поэтому я больше не буду это объяснять. Но я объясню вам кратко.
Возьмите любую небольшую программу, в которой нет петель.
{ int a=1;
print("%d",a);
}
Эта программа займет незначительное время для выполнения. Пусть декларация и печать занимают единицу времени. Таким образом, его временная сложность будет равна O (1)
Другая программа с одним циклом и выполняется в течение n раз
{int a,i;
long n=10000000;
for(i=0;i<n;i++)
// doing some calculations
}
Как можно видеть здесь, декларация займет незначительное время, то есть O (1). И если мы допустим, что эта линия 4 займет некоторую единицу времени, то есть O (n). Тогда общая временная сложность будет
O(1)+O(n)=O(n).
Теперь u может понимать для O (n * n), т.е. для 2 циклов.
Для лучшего понимания....
Поиск элемента в несортированном списке = O (n)
Умножение двух n-значных чисел на простой алгоритм или сортировку пузырьков = O (n * n)
Поиск элемента в отсортированном массиве с двоичным поиском = O (log n)
проблема продавца с грубой силой = O (n!)