Есть ли какая-либо функция в o (1)?

Ответ 1

Набор o(1) не пуст.

Прежде всего важно помнить, что f(x) находится в o(g(x)) тогда и только тогда, когда

lim_x- > бесконечность {f (x)/g (x)} = 0
Для ненулевого g (x)

Но, что более важно, каков набор кандидатов f(x)?

Некоторые определяют его по всем реальным функциям ^[1] т.е. f:R->RU{U} (где U есть undefined для некоторых значений функций). Это означает, что мы можем использовать любую вещественную и вещественную функцию, включая функцию f(x)=1/x. Мы также можем видеть, что g(x)=1 - ненулевая функция, и действительно:

lim_x- > бесконечность {1/x/1} = 0

Это означает, что o(1) включает в себя функцию f(x)=1/x, и мы можем заключить, что множество не пусто.
Knuth также ссылается на функцию g(n) = n^-1 как действительную функцию и использует O(n^-1) в его объяснение больших O, Omega и Theta (1976)

Другие, Cormen - один из них, определите множество как f: N- > N, где N = {0,1,...}, и это также включает в себя f(x)=0, в котором снова выполняется условие о (1). ^[2]

Нет алгоритма с функцией сложности T(n) в o(1)

В то время как малозначимость определена над действиями, наши функции сложности для алгоритмов не являются. Они определены над натуральными числами ^[3]. Вы либо выполняете инструкцию, либо не делаете этого. Вы не можете выполнить половину инструкции или команду e ^-1. Это означает, что набор функций сложности f:N->N. Поскольку нет такой вещи, как " пустая программа", которая не имеет инструкций (напомним, что накладные расходы, вызванные им самим, требуют времени), это даже сужает этот диапазон до f:N->N\{0}.

Другими словами, для любой функции сложности алгоритма T(n) и для всех n>0, T(n)>0.

Теперь мы можем вернуться к нашей формуле:

lim_x- > бесконечность {T (x)/1} >= lim_x- > бесконечность {1/1} = 1 > 0

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

Примечания к нотам:
(1) Если вы не уверены в этом, вспомните в серии Тейлора, в какой-то момент мы перестанем добавлять бесконечные ряды, и просто упомянем, что это O(x^n). Функция, которую мы "спрячем" в этой большой записи O, не превышает натуральные числа. (2) Если мы, однако, определим множество N + = {1,2,...} как множество положительных натуральных чисел, а o (g (n)) - подмножество положительных натуральных функций, o (1) является пустым множеством, с доказательством, идентичным тому, которое не показывает ни один алгоритм, имеет такую ​​сложность.
(3) Ну, для средних случаев изображение может быть не натуральным числом, но мы будем предполагать худшую сложность здесь, хотя претензия может сохраняться для среднего случая, так как нет пустой программы.

Ответ 2

Из определения little o следует, что для того, чтобы это условие соответствовало (будучи o (1)), должен быть алгоритм, который завершается за какое-то короткое время. Это противоречит определению машины Тьюринга, которая требует "бесконечной ленты, выделенной на квадраты (конечного размера)". Только решение для этого было бы пустой программой Turing, выполняющей команду 0.
но такая программа не может быть построена, потому что для нее потребуется машина, которая запускается в завершенном состоянии и, следовательно, не может выполнять какую-либо другую программу и не является машиной Тьюринга.

Ответ 3

Функция f (n) = 0 находится в o (1), и поэтому o (1) не пусто. Поскольку для каждого c > 0 f (n) c * 1.

Это вопрос мнения (или определения), может ли программная временная сложность быть о (1). Если вы считаете, что программа может существовать без базовых операций, тогда у нее будет сложность времени в o (1). Если вы считаете, что программа не может существовать без базовых операций, тогда она всегда будет занимать не менее 1 единицы времени независимо от ввода, а выбор c = 0,5 в определении little-o дает вам доказательство того, что его временная сложность не o (1).