почему O (1)! = O (log (n))? для n = [целое, длинное, ...]

Question

например, скажем, n = Integer.MAX_VALUE или 2 ^ 123, тогда O (log (n)) = 32 и 123, поэтому небольшое целоене так ли O (1)?

в чем разница?Я думаю, причина в том, что O (1) является постоянным, а O (log (n)) нет.Есть другие идеи?

Answer 1

Если n ограничен сверху, то классы сложности, включающие n, не имеют смысла. Не существует такого понятия, как «в пределе, когда 2 ^ 123 приближается к бесконечности», за исключением старой шутки, что «пятиугольник приближается к кругу при достаточно больших значениях 5».

Обычно, анализируя сложность кода, мы делаем вид, что размер ввода не ограничен пределами ресурсов машины, даже если это так. Это приводит к некоторым немного странным вещам, происходящим около log n, поскольку если n должен соответствовать типу int фиксированного размера, то log n имеет довольно маленькую границу, так что эта граница, скорее всего, будет полезной /relevant.

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

Например, ваша средняя быстрая сортировка формально использует стек Theta (log n) в худшем случае, очевидно, так и с довольно распространенной реализацией, в которой call-recurses на «маленькой» стороне раздела и loop-recurses на «большой» " боковая сторона. Но на 32-битной машине вы можете организовать использование массива фиксированного размера около 240 байтов для хранения «списка задач», который может быть меньше, чем какая-либо другая функция, написанная вами на основе алгоритма, формально имеющего O (1) использование стека. Мораль заключается в том, что реализация! = Алгоритм, сложность ничего не говорит вам о маленьких числах, а любое конкретное число «мало».

Если вы хотите учесть границы, вы могли бы сказать, что, например, ваш код для сортировки массива имеет время выполнения O (1), потому что массив должен быть меньше подходящего размера в адресном пространстве вашего компьютера, и, следовательно, время для его сортировки ограничено. Однако, если вы это сделаете, вы не справитесь с заданием CS и не будете никому предоставлять какую-либо полезную информацию: -)

Answer 2

Разница в том, что n не исправлено. Идея обозначения Big-O состоит в том, чтобы понять, как размер ввода влияет на время работы (или использование памяти). Поэтому, если алгоритм всегда занимает одинаковое количество времени, будь то n = 1 или n = Integer.MAX_VALUE, мы говорим, что это O(1). Если алгоритм удваивает единицу времени каждый раз, когда размер ввода удваивается, то мы говорим, что это O(logn).

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

Первый алгоритм O (n), а второй алгоритм O (nlogn). Итак, давайте начнем с массива из 16 элементов. Первый алгоритм будет работать во время 16, второй алгоритм будет работать во время 16 * 4. Если мы увеличим его до 17, то оно станет 17 и 17 * 4. Наивно можно сказать, что второй алгоритм занимает в 4 раза больше времени, чем первый (если мы рассматриваем компонент logn как константу).

Но давайте посмотрим, что происходит, когда наш массив содержит 2 ^ 32 элемента. Теперь первый алгоритм занимает 2 ^ 32 времени для завершения, тогда как наш второй алгоритм занимает 32 * 2 ^ 32 времени для завершения. Это занимает 32 раза больше времени. Да, это небольшая разница, но это все еще разница. Если первый алгоритм занимает 1 минуту, второй алгоритм займет более получаса!

Answer 3

Очевидно, что если вы знаете, что вход всегда будет иметь фиксированное количество элементов, алгоритм всегда будет работать в постоянное время.Обозначение Big-O используется для обозначения худшего случая времени работы, которое описывает предел, когда количество элементов становится бесконечно большим.

Answer 4

Я думаю, что вы получите лучшее представление, если оно называется O(n^0).

Это функция масштабирования в зависимости от входной переменной N,Это функция, а не число, вы никогда не должны принимать любое число для переменной N.

Это так же, как если бы вы сказали, что функция f(x) равна 3, потому что f(100) = 3, это неправильно,Это функция, а не какой-то конкретный номер.Постоянная функция f(x) = 1 по-прежнему является функцией, она никогда не будет равна другой функции g(x) = N, т.е. g(x)=f(x)

Answer 5

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

Answer 6

Big-O показывает, как время работы (или память и т. Д.) изменяется при изменении размера проблемы.Когда размер задачи становится в 10 раз больше, решение O (n) занимает в 10 раз больше времени, решение O (log (n)) занимает немного больше времени, а решение O (1) занимает то же время: O (1) означает «изменяется так же быстро, как и константа 1», но константы не меняются.

Ознакомьтесь с обозначением big-O чуть подробнее .

Answer 7

Вы не думаете достаточно широко. Любой алгоритм, работающий на компьютере, будет работать вечно или завершаться через некоторое небольшое количество шагов - поскольку компьютер является конечным автоматом, вы не можете писать алгоритмы, которые запускаются в течение произвольного количества времени, а затем завершаются. По этому аргументу нотация Big-O носит только теоретический характер и не имеет смысла в реальной компьютерной программе. Даже O(2^n) достигает верхнего предела в O(2^INT_MAX), что эквивалентно O(1).

Реально, однако, Big-O может помочь вам, если вы знаете постоянные факторы. Даже если алгоритм имеет верхнюю границу O(log n), а n может иметь 32 бита, это может означать разницу между запросом, занимающим 1 секунду и 32 секунды.

Answer 8

Существует причина, по которой вы оставляете "O (n)" и рассматриваете возможность удаления "O (log n)". Они оба являются "константами": первое меньше 32, а второе меньше 2 ³² . Но тем не менее у вас есть естественное чувство, что вы не можете назвать O (n) O (1).

Однако, если log(n) < 32, это означает, что алгоритм O (n * logn) работает в тридцать два раза медленнее , чем его версия O (n). Достаточно большой, чтобы написать "log * n" s?