Итак, быстрая мысль; Можно ли утверждать, что O(∞) на самом деле равно O(1)?
- Я имею в виду, что это не зависит от размера ввода?
- Так что в некотором роде она постоянна, хотя и бесконечна.
Или единственный «правильный» способ выразить это O (∞)?
O-обозначение, O(∞) = O(1)?
Ответы (4)
Бесконечность — это не число или, по крайней мере, не действительное число, поэтому выражение имеет неверный формат. Правильный способ выразить это — просто указать, что программа не завершается. Примечание: программа, а не алгоритм, так как алгоритм гарантированно завершится.
(Если вы хотите, вы можете определить нотацию большого O для трансфинитных чисел. Однако я не уверен, что это будет полезно.)
person
Fred Foo
schedule
11.04.2011
Ваша точка зрения, конечно, верна, она в некотором роде выходит за рамки определения, но использование o (бесконечность) в качестве времени выполнения не завершающей программы - это просто соглашение, которое иногда используется.
- person Peter; 12.04.2011
@Peter: я никогда этого не видел. Меня бы это смутило, и я думаю, что я не единственный :)
- person Fred Foo; 12.04.2011
en.wikipedia.org/wiki/Bogosort, как указано, но кроме того, я согласен, я я тоже не фанат этого.
- person Peter; 12.04.2011
@Peter: ах, я не заметил инфобокс. (Странно: в программировании на Прологе bogosort — это название однострочника, который сортирует путем обхода всех перестановок,
sort(Lst,Srt) :- permutation(Lst,Srt), sorted(Srt)., который выполняется за O(n!).)
- person Fred Foo; 12.04.2011
Да, но сортировка по совпадению конечно может быть намного хуже всех перестановок, бесконечная - это WCS, а не среднее. Очевидно, одно и то же имя для разных вещей; интересная информация однако.
- person Peter; 12.04.2011
Ваш аргумент не совсем корректен.
Обозначение Big O игнорирует константы, кратные; нет никакой разницы между O(1) и O(42) или между O(log(n)) и O(3π log(n)) .
Стандартное соглашение состоит в том, чтобы не использовать какие-либо постоянные кратные числа.
Однако O(∞) будет означать "алгоритм", который никогда не завершается, в отличие от O(1), который завершается в какой-то момент.
person
SLaks
schedule
11.04.2011
Алгоритм, который никогда не завершается, формально не является алгоритмом (независимо от того, насколько он полезен).
- person Fred Foo; 12.04.2011
Как насчет
strlen в C, когда ему не задана строка, заканчивающаяся NUL, в которой есть бесконечная память и нет нулей? Чисто гипотетически, но считается ли это?
- person ; 27.06.2011
Чтобы ответить на вопрос:
O-обозначение, O(∞) = O(1)?
Нет
Основное отличие состоит в том, что O(1) закончится в какой-то момент, а O(∞) никогда не закончится.
Оба они не включают переменную, но имеют разные значения:
O(1) (или O(121) или O(что угодно, но не бесконечность): не зависит от аргументов функции, но заканчивается
O(∞) : не зависит от аргументов функции и не заканчивается
Как указано в другом ответе, бесконечность на самом деле не относится к области обозначения большого O, но, конечно, остается простое «нет», O (1) и O (∞) не одно и то же.
person
Peter
schedule
11.04.2011
Big-Oh — это мера того, как масштабируются требуемые ресурсы по мере увеличения N. O(5 часов) и O(5 секунд) равны O(1), так как при увеличении N не требуются дополнительные ресурсы.
person
ikegami
schedule
11.04.2011
O(infinity). - person schedule 12.04.2011