Я видел этот термин «время доступа O (1)» означает «быстро», но я не понимаю, что это значит. Другим термином, который я вижу с ним в том же контексте, является «время доступа O (n)». Может ли кто-нибудь объяснить простой способ, что означают эти термины?Что означает «время доступа O (1)»?
Смотрите также
Вы хотите ознакомиться с порядком сложности.
http://en.wikipedia.org/wiki/Big_O_notation
Короче говоря, O (1) означает, что она занимает постоянное время, как 14 наносекунд, или три минуты независимо от количества данных в наборе.
O (n) означает, что требуется количество времени, линейное с размером набора, поэтому набор в два раза больше, чем в два раза. Вероятно, вы не хотите помещать миллион объектов в один из них.
Чтобы быть педантичным, это не означает, что время выполнения (или количество операций и т. Д.) Является постоянным. Это означает, что существует константа, так что время выполнения (или количество операций и т. Д.) Ограничено константой. В среде выполнения все еще может быть большая дисперсия: например, 'int main() {int n; cin >> n; if (n == 0) {sleep (60 * 60 * 24 * 365); } cout << n; } 'is' O (1) '. – jason
В сущности, это означает, что она занимает такое же количество времени, чтобы посмотреть значение в вашей коллекции есть ли у вас небольшое количество предметов в вашей коллекции или очень много (в рамках ограничений вашего оборудования)
O (n) означает, что время, необходимое для поиска элемента, пропорционально количеству элементов в коллекции.
Типичными примерами этого являются массивы, к которым можно получить доступ напрямую, независимо от их размера и связанных списков, которые должны быть пройдены в порядке от начала для доступа к данному элементу.
Другая операция обычно обсуждается - вставка. Коллекция может быть O (1) для доступа, но O (n) для вставки. На самом деле массив имеет именно такое поведение, потому что для вставки элемента в середине вам нужно будет переместить каждый элемент вправо, скопировав его в следующий слот.
Это означает, что время доступа постоянное. Независимо от того, используете ли вы 100 или 100 000 записей, время поиска будет таким же.
Напротив, время доступа O (n) указывает, что время поиска прямо пропорционально количеству записей, к которым вы обращаетесь.
O (1) означает, что время доступа к чему-то не зависит от количества предметов в коллекции.
O (N) означает, что время доступа к элементу пропорционально количеству (N) элементов в коллекции.
Это означает, что доступ занимает постоянное время, то есть не зависит от размера набора данных. O (n) означает, что доступ будет зависеть от размера набора данных линейно.
O также известен как большой-O.
Он называется Big O notation и описывает время поиска для различных алгоритмов.
O (1) означает, что время работы наихудшего случая является постоянным. Для большинства ситуаций это означает, что вам не нужно искать коллекцию, вы можете быстро найти то, что ищете.
Заменить «время поиска» на «наихудший вариант» время ", и я с тобой. –
@Seb: Я думаю, что это было просто неправильное имя с его стороны, в частности потому, что OP спросил о времени доступа. – jkeys
«Обозначение большого О» - способ выразить скорость алгоритмов. n - количество данных, с которыми работает алгоритм. O(1) означает, что, независимо от того, сколько данных он будет выполнять в постоянное время. O(n) означает, что он пропорционален количеству данных.
В основном, O (1) означает, что его время вычисления является постоянным, в то время как О (п) означает, что она будет зависеть линейно от размера входного - т.е. цикл через массив имеет О (п) - просто цикл -, потому что это зависит от количества элементов, а вычисление максимума между обычными числами имеет O (1).
Википедия может помочь также: http://en.wikipedia.org/wiki/Computational_complexity_theory
Самый простой способ отличить O (1) и O (п) сравнивает массив и список.
Для массива, если у вас есть правильное значение индекса, вы можете мгновенно получить доступ к данным. (Если вы не знаете индекс и должны пройти через массив, то он больше не будет O (1))
Для списка вам всегда нужно прокручивать его, знаете ли вы индекс или не.
Я искал пример O (1), и только для этого ответа есть объяснение. – neelmeg
O (1) не обязательно означает «быстро». Это означает, что время, которое требуется, является постоянным, и не в зависимости от размера ввода функции. Константа может быть быстрой или медленной. O (n) означает, что время, которое займет функция, будет меняться прямо пропорционально размеру ввода функции, обозначаемому n. Опять же, это может быть быстрым или медленным, но оно будет замедляться по мере увеличения размера n.
Введение в алгоритмы: Second Edition по Cormen, Leiserson, Ривестом & Штейн говорит на странице 44, что
Поскольку любая константа является степенью 0 многочлен, мы можем выразить любую постоянную функцию как Theta (n^0), или Theta (1). Эта последняя нотация является незначительным злоупотреблением , однако, поскольку это непонятно, какая переменная имеет тенденцию бесконечность. Мы будем часто использовать обозначение Theta (1), обозначающее константу или постоянную функцию с относительно некоторой переменной. ... We обозначим через O (g (n)) ... набор функций f (n) таких, что существуют положительные константы c и n0 такие, что = f (n) < = c * g (n) для всех n> = n0. ... Заметим, что f (n) = Theta (g (n)) подразумевает f (n) = O (g (n)), так как обозначение Theta сильнее обозначений O.
Если алгоритм работает в O (1) времени, это означает, что асимптотически не зависит от любой переменной, а это означает, что существует по крайней мере одна положительная константа, что при умножении на единицу больше, чем асимптотической сложности (~ runtime) функции для значений n выше определенной суммы. Технически это время O (n^0).
O (1) означает случайный доступ.В любой памяти произвольного доступа время, затрачиваемое на доступ к любому элементу в любом месте, одинаково. Здесь время может быть любым целым числом, но единственное, что нужно запомнить, - это время, затраченное на извлечение элемента в (n-1) th или n-м месте, будет таким же (т.е. постоянным).
Принимая во внимание, что O (n) зависит от размера n.
Это не имеет никакого отношения к случайному доступу - см. [Принятый ответ] (http://stackoverflow.com/a/697935/836214), опубликованный почти за год до этого ответа для получения дополнительной информации. – Krease
Каждый ответ, отвечающий на этот вопрос, сообщает вам, что 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) означает, что время, чтобы выполнить одну операции или команду в то время, это один, во время анализа сложности алгоритма для наилучшего случая.
Постарайтесь усерднее. Этот конкретный вопрос требует не просто перспективы, но четкого определения. – Alfabravo
Что я только что прочитал? Обыватель – shashwatZing
O(1) всегда выполняется в одно и то же время независимо от набора данных n. Примером O (1) будет ArrayList, получающий его элемент с индексом.
O(n) также известный как линейный заказ, производительность будет расти линейно и прямо пропорционально размеру входных данных. Примером O (n) является вставка и удаление ArrayList в случайной позиции. Поскольку каждая последующая вставка/удаление в случайном положении приведет к тому, что элементы в ArrayList будут перемещаться влево-вправо от внутреннего массива, чтобы сохранить свою линейную структуру, не говоря уже о создании новых массивов и копировании элементов из старого к новому массиву, который занимает дорогостоящее время обработки, что ухудшает производительность.
Это может помочь: http://stackoverflow.com/questions/471199/what-is-the-difference-between-n-and-on/471206#471206 –