infinity - O表記、O(∞)=O(1)?

Question

簡単な考えです。O(∞) は実際には O(1) であると主張できますか?

• 入力サイズに依存しないということですか？
• したがって、無限であるにもかかわらず、ある意味で一定です。

それとも、それを表現する唯一の「正しい」方法は O(∞) ですか?

Answer 1

Infinity は数値ではないか、少なくとも実数ではないため、式の形式が正しくありません。これを表現する正しい方法は、単にプログラムが終了しないことを示すことです。注:アルゴリズムは終了することが保証されているため、algorithmではなくprogramを使用してください。

（必要に応じて、超限数に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 が増加しても余分なリソースが必要ないためです。