Я видел, что этот термин "время доступа O (1)" означает "быстро", но я не понимаю, что это значит. Другим термином, который я вижу с ним в том же контексте, является "время доступа O (n)". Может ли кто-нибудь объяснить простой способ, что означают эти термины?
См. также
Вы хотите прочитать "Порядок сложности".
http://en.wikipedia.org/wiki/Big_O_notation
Короче говоря, O (1) означает, что он принимает постоянное время, например 14 наносекунд, или три минуты независимо от количества данных в наборе.
O (n) означает, что он занимает некоторое количество времени, линейное с размером набора, поэтому набор в два раза превышает размер в два раза. Вероятно, вы не хотите помещать миллион объектов в один из них.
В сущности, это означает, что для поиска значения в вашей коллекции требуется столько же времени, сколько у вас небольшое количество элементов в вашей коллекции или очень много (в пределах ограничений вашего оборудования)
O (n) означает, что время, необходимое для поиска элемента, пропорционально количеству элементов в коллекции.
Типичными примерами этого являются массивы, к которым можно получить доступ напрямую, независимо от их размера и связанных списков, которые должны быть пройдены в порядке от начала для доступа к данному элементу.
Другая операция, обычно обсуждаемая, - вставка. Коллекция может быть O (1) для доступа, но O (n) для вставки. На самом деле массив имеет именно такое поведение, потому что для вставки элемента в середине вам нужно будет переместить каждый элемент вправо, скопировав его в следующий слот.
Каждый ответ, отвечающий на этот вопрос, говорит вам, что O(1) означает постоянное время (независимо от того, что происходит с измерением, может быть время выполнения, количество операций и т.д.). Это неверно.
Сказать, что время выполнения O(1) означает, что существует константа c, так что время выполнения ограничено выше c, независимо от ввода. Например, возврат первого элемента массива из n целых чисел составляет O(1):
int firstElement(int *a, int n) {
return a[0];
}
Но эта функция тоже O(1):
int identity(int i) {
if(i == 0) {
sleep(60 * 60 * 24 * 365);
}
return i;
}
Время выполнения здесь ограничено на 1 год, но в большинстве случаев время выполнения составляет порядка наносекунд.
Сказать, что время выполнения O(n) означает, что существует константа c, так что среда выполнения ограничена выше c * n, где n измеряет размер ввода. Например, поиск числа вхождений определенного целого числа в несортированном массиве целых чисел n по следующему алгоритму: O(n):
int count(int *a, int n, int item) {
int c = 0;
for(int i = 0; i < n; i++) {
if(a[i] == item) c++;
}
return c;
}
Это связано с тем, что мы должны проходить через массив, проверяя каждый элемент по одному.
O (1) не обязательно означает "быстро". Это означает, что время, которое требуется, является постоянным и не на основе размера ввода функции. Константа может быть быстрой или медленной. O (n) означает, что время, которое займет функция, будет меняться прямо пропорционально размеру ввода функции, обозначаемому n. Опять же, это может быть быстрым или медленным, но оно будет замедляться по мере увеличения размера n.
O (1) означает, что время доступа к чему-либо не зависит от количества элементов в коллекции.
O (N) означает, что время доступа к элементу пропорционально количеству (N) элементов в коллекции.
Он назвал нотацию Big O и описывает время поиска для различных алгоритмов.
O (1) означает, что время выполнения наихудшего случая является постоянным. Для большинства ситуаций это означает, что вам не нужно искать коллекцию, вы можете быстро найти то, что ищете.
"Большая нотация" - способ выразить скорость алгоритмов. n - количество данных, с которыми работает алгоритм. O(1) означает, что независимо от того, сколько данных он будет выполняться в течение постоянного времени. O(n) означает, что он пропорционален количеству данных.
В основном, O (1) означает, что его время вычисления является постоянным, а O (n) означает, что он будет зависеть от размера ввода, т.е. цикл через массив имеет O (n) - просто цикл -, потому что это зависит по числу элементов, а при вычислении максимума между обычными числами имеет O (1).
Википедия также может помочь: http://en.wikipedia.org/wiki/Computational_complexity_theory
O(1) всегда выполняется в одно и то же время независимо от набора данных n.
Примером O (1) будет ArrayList, получающий его элемент с индексом.
O(n), также известный как линейный порядок, производительность будет расти линейно и прямо пропорционально размеру входных данных.
Примером O (n) будет вставка и удаление ArrayList в случайной позиции. Поскольку каждая последующая вставка/удаление в случайном положении приведет к тому, что элементы в ArrayList будут перемещаться влево-вправо от внутреннего массива, чтобы сохранить свою линейную структуру, не говоря уже о создании новых массивов и копировании элементов из старого к новому массиву, который требует дорогостоящего времени обработки и снижает производительность.
Это означает, что время доступа является постоянным. Если вы получаете доступ к 100 или 100 000 записей, время поиска будет таким же.
Напротив, время доступа O (n) указывает, что время поиска прямо пропорционально количеству записей, к которым вы обращаетесь.
Это означает, что доступ занимает постоянное время, то есть не зависит от размера набора данных. O (n) означает, что доступ будет зависеть от размера набора данных линейно.
O также известен как большой-O.
Самый простой способ отличить O (1) и O (n) - это сравнение массива и списка.
Для массива, если у вас есть правильное значение индекса, вы можете мгновенно получить доступ к данным. (Если вы не знаете индекс и должны пройти через массив, то он больше не будет O (1))
Для списка вам всегда нужно прокручивать его, знаете ли вы индекс или нет.
Введение в алгоритмы: второе издание Cormen, Leiserson, Rivest и Stein говорит на стр. 44, что
Так как любая константа является степенью-0 полином, мы можем выразить любые постоянной функции как Theta (n ^ 0), или Тета (1). Это последнее обозначение незначительное злоупотребление, однако, поскольку оно неясно, какая переменная имеет тенденцию бесконечность. Мы часто будем использовать обозначение Theta (1) означает либо постоянная или постоянная функция с относительно некоторой переменной.... Мы обозначим через O (g (n))... множество функции f (n) такие, что существуют положительные константы c и n0 такие, что 0 <= f (n) <= c * g (n) для всех n >= n0.... Заметим, что f (n) = Theta (g (n)) означает f (n) = O (g (n)), так как Theta нотация более сильная, чем обозначение O.
Если алгоритм работает в O (1) раз, это означает, что асимптотически не зависит от какой-либо переменной, а это означает, что существует по крайней мере одна положительная константа, которая при умножении на единицу больше, чем асимптотическая сложность (~ время выполнения) функции для значений n выше определенной величины. Технически это время O (n ^ 0).
O (1) означает случайный доступ. В любой памяти произвольного доступа время, затрачиваемое на доступ к любому элементу в любом месте, одинаково. Здесь время может быть любым целым числом, но единственное, что нужно запомнить, - это время, затраченное на извлечение элемента в (n-1) th или n-м месте, будет таким же (т.е. постоянным).
В то время как O (n) зависит от размера n.
Согласно моей перспективе,
O (1) означает, что время для выполнения одной операции или команды за один раз является одним, при анализе временной сложности алгоритма для наилучшего случая.