Что делает “O (1) время доступа”, среднее?

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

O также известен как большой-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) = Тета (g (n)) подразумевает f (n) = O (g (n)), так как нотация Теты более сильна, чем нотация O.

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

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

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

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

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

Для списка всегда необходимо циклично выполняться через него, знаете ли Вы индекс или нет.

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

Википедия могла бы помочь также: http://en.wikipedia.org/wiki/Computational_complexity_theory

Это назвало Большую нотацию O и описывает время поиска для различных алгоритмов.

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

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

O (1) означает, что время для доступа к чему-то независимо от количества объектов в наборе.

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

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

В сущности Это означает, что это занимает то же количество времени для поиска значения в наборе, есть ли у Вас небольшое количество объектов в Вашем наборе или очень очень многих (в рамках ограничений Ваших аппаратных средств)

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

Типичными примерами их являются массивы, к которым можно получить доступ непосредственно, независимо от их размера и связанных списков, которые должны быть пересечены в порядке с начала получить доступ к данному объекту.

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

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

В то время как O (n) зависит от размера n.

Я обнажил свою версию Haskell на днях, так непроверенную, но следующее кажется немного проще, чем другие (использует сопоставление образцов и падение, чтобы избежать застежка -молния и mod):

everynth :: Int -> [a] -> [a]
everynth n xs = y : everynth n ys
         where y : ys = drop (n-1) xs

Однако, я знаю, что некоторые компиляторы выйдут из логического выражения полностью, если первое условие не сработает. Верно ли это для Java?

Да, это называется Оценка короткого замыкания .Операторы, такие как & & и | | , являются операторами, выполняющими такие операции.

Или порядок оценки не гарантирован?

Нет, порядок оценки гарантирован (слева направо)

Каждый ответ на этот вопрос говорит вам, что 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;
}

Это потому, что мы должны выполнить итерацию через массив, проверяя каждый элемент по одному.