O-обозначение, O (∞) = O (1)?

Question

Итак, быстрая мысль; Можно ли утверждать, что O (∞) на самом деле является O (1)?

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

Или это единственный «правильный» способ выразить это O (∞)?

Answer 1

Бесконечность не является числом или, по крайней мере, не действительным числом , поэтому выражение искажено. Правильный способ выразить это - просто заявить, что программа не завершается. Примечание: программа , а не алгоритм , поскольку алгоритм гарантированно завершится.

(При желании вы могли бы определить нотацию big-O для трансфинитных чисел. Хотя я не уверен, что это будет полезно.)

Answer 2

Ваш аргумент не совсем корректен.

Обозначение Big O игнорирует постоянные кратные числа;нет никакой разницы между O(1) и O(42) или между O(log(n)) и O(3π log(n)).

Стандартным соглашением является не использовать постоянные кратные значения.

Однако O(∞) будетозначает «алгоритм», который никогда не завершается, в отличие от O(1), который в какой-то момент завершится.

Answer 3

Чтобы ответить на вопрос:

O-запись, O (∞) = O (1)?

нет

Нет

Основное отличие состоит в том, что O (1) заканчивается в некоторой точке, а O (∞) никогда не заканчивается.

Они оба не включают переменную, но имеют оба разных значения:

O(1) (или O (121) или O (независимо от бесконечности): независимо от аргументов функций, но заканчивается

O(∞): независимо от аргументов функций и без окончания

Как указывалось в другом ответе, бесконечность в действительности не входит в область обозначения big-O, но простое «нет», чем остается, конечно, O (1) и O (∞) не одно и то же.

Answer 4

Big-Oh - это показатель того, как требуемые ресурсы масштабируются по мере увеличения N.O (5 часов) и O (5 секунд) - это O (1), поскольку при увеличении N не требуется никаких дополнительных ресурсов.