Ответ 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) Ну, для средних случаев изображение может быть не натуральным числом, но мы будем предполагать худшую сложность здесь, хотя претензия может сохраняться для среднего случая, так как нет пустой программы.