私の同僚が私に質問をしてきました: セットo(1)(小さな o 記法) は空ですか?
私の質問は:o(1)空集合ですか? o(1)そうでない場合、時間の複雑さを持つプログラムはありますか?
リマインダー、 Cormenによる little-o の定義:
任意の正の定数に対して、すべてに対して という定数が存在する場合、その関数は存在すると
f(n)言われます。o(g(n))c>0n0 > 00 <=f(n) < cg(n)n>= n0
直観的に、if it is in ですf(n)が、この境界は厳密ではありません。o(g(n))O(g(n))
セットo(1)は空ではありません。
if and only iff(x)にあることを覚えておくことが最初に重要ですo(g(x))
lim_x->infinity { f(x) / g(x)} = 0
非ゼロ g(x) の場合
しかし、もっと重要なのは、候補のセットは何f(x)ですか?
すべての実関数 [1]に対して定義するものもあります [1] f:R->RU{U}。これは、 function を含む実数から実数への関数を使用できることを意味しますf(x)=1/x。g(x)=1また、それが非ゼロ関数であることもわかります。実際、次のようになります。
lim_x->無限 { 1/x / 1} = 0
これはo(1)、関数 が含まれていることを意味し、f(x)=1/xセットは空ではないと結論付けることができます。
クヌースもこの関数g(n) = n^-1を有効な関数と呼んでおり、大きな O、Omega、Theta (1976) の説明でO(n^-1)使用しています。
その他、Cormen はその 1 つであり、セットを f:N->N として定義します。ここで、N={0,1,...} です。これにはf(x)=0、o(1) であるという条件を保持する も含まれます。[2]
T(n)複雑な機能を持つアルゴリズムはありませんo(1)
実数に対する o 表記はほとんど定義されていませんが、アルゴリズムの複雑度関数は定義されていません。それらは自然数で定義されます[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) 平均的なケースでは、画像は非自然数になる可能性がありますが、ここでは最悪の場合の複雑さを想定しますが、空のプログラムは存在しないため、平均的なケースでも主張は成り立ちます。
関数 f(n)=0 は o(1) にあるため、o(1) は空ではありません。すべての c>0 について、f(n) < c * 1 であるためです。
プログラムの時間計算量が o(1) になるかどうかは、意見 (または定義) の問題です。プログラムが基本的な操作なしで存在できると考える場合、o(1) では時間の複雑さが発生します。プログラムが基本的な操作なしでは存在できないと考える場合、入力に関係なく常に少なくとも 1 時間単位が必要であり、little-o の定義で c=0.5 を選択すると、その時間計算量がo(1) ではありません。
の定義から、little oこの条件を満たす (o(1) である) ためには、任意の短い時間で完了するアルゴリズムが存在する必要があります。
これは、「（有限サイズの）正方形にマークされた無限のテープ」を必要とするチューリングマシンの定義と矛盾します。これに対する唯一の解決策は、0命令を実行する空のTuringプログラムです。
しかし、そのようなプログラムは、終了状態で起動し、他のプログラムを実行できず、チューリングマシンではないマシンを必要とするため、ビルドできません。