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

https://stackoverflow.com/questions/697918

big-o

22-08-2019
|

Вопрос

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

Смотрите также

Что такое Big O обозначения? Вы используете это?

Биг-о для восьмилетних?

Решение

Вы захотите прочитать по заказу сложности.

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) элементов в коллекции.

O (1) не обязательно означает «быстро». Это означает, что время, которое он занимает, постоянно, и нет на основе размера ввода в функцию. Постоянный может быть быстрым или медленным. O (n) означает, что время, которое выполняет функция, будет изменяться прямо пропорционально размеру ввода в функцию, обозначаемое n. Опять же, это может быть быстро или медленнее, но он будет медленнее с увеличением размера n.

Это называется Большой О записка, и описывает время поиска различных алгоритмов.

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

«Большой О записка» - это способ выразить скорость алгоритмов. n это объем данных, с которыми работает алгоритм. O(1) означает, что независимо от того, сколько данных он будет выполняться в постоянное время. O(n) означает, что это пропорционально количеству данных.

O(1) Всегда выполняйте в одно и то же время независимо от набора данных n. Примером O (1) будет ArrayList, доступ к которому с помощью указателя.

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

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

Википедия может также помочь: http://en.wikipedia.org/wiki/computational_complexity_theory

Самый простой способ дифференцировать O (1) и O (n) - это сравнение массива и списка.

Для массива, если у вас есть правильное значение индекса, вы можете немедленно получить доступ к данным. (Если вы не знаете индекс и должны пройти через массив, то это больше не будет O (1))

Для списка вам всегда нужно пройти через него, знаете ли вы индекс или нет.

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

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

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

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

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

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

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

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

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

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

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

Согласно моей точке зрения,

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow