Что означает «время доступа O (1)»?

Question

Я видел, как этот термин «O (1) время доступа» имел обыкновение означать «быстро», но я не понимаю, что это значит. Другой термин, который я вижу в этом же контексте: «O (n) access time». Может ли кто-нибудь объяснить простым способом, что означают эти термины?

См. Также

• Что такое обозначение Big O? Вы используете это?
• Big-O для восьмилетних?

Answer 1

Введение в алгоритмы: второе издание Cormen, Leiserson, Rivest & Stein говорит на странице 44, что

Поскольку любая константа имеет степень 0 полином, мы можем выразить любой постоянная функция как тета (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 (1) времени, это означает, что асимптотически не зависит от какой-либо переменной, то есть существует хотя бы одна положительная константа, которая при умножении на единицу больше, чем асимптотическая сложность (~ время выполнения) функции для значений n выше определенной суммы. Технически это время O (n ^ 0).

Answer 2

Это означает, что доступ занимает постоянное время, то есть не зависит от размера набора данных. O (n) означает, что доступ будет зависеть от размера набора данных линейно.

O также известен как big-O.

Answer 3

Это означает, что время доступа постоянно. Независимо от того, получаете ли вы доступ из 100 или 100 000 записей, время поиска будет одинаковым.

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

Answer 4

Вот простая аналогия; Представьте, что вы загружаете фильмы онлайн с помощью O (1), если загрузка одного фильма занимает 5 минут, загрузка 20 фильмов все равно займет то же время. Таким образом, не имеет значения, сколько фильмов вы загружаете, они займут одно и то же время (5 минут), будь то один или 20 фильмов. Обычный пример этой аналогии - когда вы идете в библиотеку фильмов, берете ли вы один фильм или 5, вы просто выбираете их сразу. Следовательно, тратя то же самое время.

Однако при использовании O (n), если загрузка одного фильма занимает 5 минут, загрузка 10 фильмов занимает около 50 минут. Поэтому время не является постоянным или пропорционально количеству загружаемых фильмов.

Answer 5

По моему мнению,

O (1) означает, что время выполнения одной операции или инструкции за один раз - во время анализа сложности алгоритма для наилучшего случая.

Answer 6

O (1) означает произвольный доступ. В любой оперативной памяти время доступа к любому элементу в любом месте одинаково. Здесь время может быть любым целым числом, но единственное, что нужно помнить, это время, необходимое для извлечения элемента в (n-1) -й или n-й позиции, которое будет одинаковым (т.е. постоянным).

Тогда как O (n) зависит от размера n.