algorithm - O(2/n) と O(1) の時間計算量を比較

Question

O(2/n) と O(100) の時間複雑度を持つ 2 つの関数がある場合。実行時間が短い関数はどれですか? 時間計算量が 2/n である実関数はありますか? （アルゴリズムの質問紙でこれを見つけました）

Answer 1

まず、O 表記法 (およびシータとオメガ) では、定義に既に "for some constant k " という部分が含まれているため、任意の定数を無視できます。

したがって、基本的に、O(100) は O(1) に相当し、O(2/n) は O(1/n) に相当します。どちらが実行時間が速いか - nに依存します。100と2/nを直接使用して実行時間を計算すると仮定すると、実行時間は次のようになります。

• すべてのケースでO(100)に対して100 (時間単位)
• n < 0.02でO(2/n)で100 (時間単位)以上
• n >= 0.02の場合、 O(2/n)の場合は100 (時間の単位)未満

さて、この質問が純粋に理論的なものであることを願っています。実際には、O(1/n) の複雑さを持つアルゴリズムは存在しないためです。これは、時間がかからないことを意味します(データ量あたりの時間に注意してください。それは単なる時間です)。処理する必要があるより多くのデータ。これが明確であることを願っています。無限の量のデータに対して0時間かかるアルゴリズムはないということです。

もう 1 つの複雑さである O(100) は、入力データが何であれ同じ手順を実行するアルゴリズムであるため、実行時間は常に一定です (実際には、定数によって制限されるだけで、より高速に実行できます)。それは時々）。例として、整数のファイルから入力を読み取り、そのファイルの最初の 100 個の数値の合計、または 100 個の数値が存在しない場合はすべての数値の合計を返すプログラムがあります。常に最大 100 個の数値 (残りは無視できます) を読み取り、それらを合計するため、定数のステップ数によって制限されます。

Answer 2

私はO(2/n)実行時間のあるアルゴリズムに精通しておらず、存在する可能性があるとは思えませんが、数学的な問題を見てみましょう。

数学的な問題は次のようになります: (1) は¹O(2/n)の部分集合です(2)の部分集合ですか?O(1)O(1)O(2/n)

1. はい。これは、定数 c,N があり、 for each : であることを意味しf(n)ます。for each 、したがってfor eachなどの定数もあります。のサブセットも同様ですO(2/n)n > Nc*f(n) < 2/nc2,N2c*2/n < 1n > N2min{c1,c2} * f(n) < 1n > max{N1,N2}O(2/n)O(1)

2. いいえ。lim(2/n) = 0無限大でc,Nはn>N、2/n < 1*cそれぞれのf(n) = 2/nO(1)O(2/n)

結論: ある機能もあるO(2/n)がO(1)、その逆ではない。
つまり、O(2/n)スケール内の各関数は 1 よりも「小さい」ということです。

---

(1) と同じですO(100)。O(1) = O(100)

Answer 3

何でもできるアルゴリズムはO(2/n)事実上不可能です。

アルゴリズムは、結果を生成する一連の有限のステップです。コンピューターの「ステップ」には一定の時間 (たとえば、少なくとも 1 つの CPU サイクル) がかかるため、アルゴリズムが時間を持つことができる唯一の方法は、O(2/n)十分に大きな. したがって、何もしません。n

アルゴリズムと時間の複雑さは別として、O(2/n)関数は「より小さい」定数です。つまり、O(2/n)n が無限大になる傾向があるため、関数は必ず 0 になる傾向がありますが、O(1)関数は必ずしもそうではありません。

この論文からの質問のテキストに関するコメント: である関数O(100)はまたO(1)であり、である関数O(2/n)はまたO(1/n)です。不必要な定数を含む big-O を書くのはあまり意味がありませんが、これは試験なので、おそらく混乱を招く可能性があります。

Answer 4

確かにそれは N の値に依存します。O(100) は基本的に固定された時間であり、n の値に応じて O(2/N) よりも速くまたは遅く実行される場合があります。

O(2/N) アルゴリズムをすぐに思いつくことはできません。データが増えるほど高速になるものです...少し奇妙に聞こえます。