354

O(1/n) アルゴリズムはありますか?

または、O(1) 未満のものはありますか?

4

32 に答える 32

329

この質問は、一部の人に思われるほどばかげているわけではありません。少なくとも理論的には、O (1/ n ) のようなものは、 Big O 表記の数学的定義を取ると完全に理にかなっています。

これで、1/ xをg ( x )に簡単に置き換えることができます。上記の定義が一部のfにも当てはまることは明らかです。

漸近的なランタイムの成長を推定する目的では、これは実行可能性が低くなります...意味のあるアルゴリズムは、入力が大きくなるにつれて速くなることはありません. 確かに、これを満たすために任意のアルゴリズムを構築できます。たとえば、次のようなものです。

def get_faster(list):
    how_long = (1 / len(list)) * 100000
    sleep(how_long)

明らかに、この関数は、入力サイズが大きくなるにつれて、より短い時間を費やします... 少なくとも、ハードウェアによって強制される何らかの制限 (数値の精度、sleep待機できる最小時間、引数を処理する時間など) まで: この制限は、その後、定数の下限であるため、実際には上記の関数にはまだランタイムO (1) があります。

しかし、実際には、入力サイズが増加すると実行時間が (少なくとも部分的に) 減少する現実世界のアルゴリズムがあります。ただし、これらのアルゴリズムはO (1)未満では実行時の動作を示さないことに注意してください。それでも、それらは興味深いものです。たとえば、Horspoolによる非常に単純なテキスト検索アルゴリズムを取り上げます。ここで、検索パターンの長さが長くなるにつれて、予想される実行時間は減少します (ただし、干し草の山の長さが長くなると、実行時間は再び増加します)。

于 2009-05-25T08:10:15.847 に答える
155

はい。

ランタイム O(1/n) を使用するアルゴリズムは、正確に 1 つ、「空の」アルゴリズムです。

アルゴリズムが O(1/n) であるということは、単一の命令で構成されるアルゴリズムよりも少ないステップで漸近的に実行されることを意味します。すべての n > n0 に対して 1 ステップよりも少ないステップで実行する場合、それらの n に対して正確にまったく命令から構成されていない必要があります。「if n > n0」のチェックには少なくとも 1 つの命令が必要なため、すべての n に対して命令が含まれていてはなりません。

要約: O(1/n) である唯一のアルゴリズムは、命令を含まない空のアルゴリズムです。

于 2009-06-11T17:40:02.927 に答える
23

それは可能ではありません。Big-O の定義は、以下の不等式です。

A(n) = O(B(n))
<=>
exists constants C and n0, C > 0, n0 > 0 such that
for all n > n0, A(n) <= C * B(n)

したがって、B(n) は実際には最大値であるため、n が増加しても B(n) が減少する場合、推定値は変わりません。

于 2009-05-25T06:21:23.840 に答える
8

いいえ、これは不可能です:

n は 1/n で無限大になる傾向があるため、最終的に 1/(inf) を達成します。これは事実上 0 です。

したがって、この問題の大きなクラスは、大規模な n では O(0) になりますが、n が小さいと定数時間に近くなります。一定時間よりも速く実行できる唯一のことは次のとおりであるため、これは賢明ではありません。

void nothing() {};

そして、これでさえ議論の余地があります！

コマンドを実行するとすぐに、少なくとも O(1) になるので、O(1/n) の大きなクラスを持つことはできません。

于 2009-05-25T12:45:40.597 に答える
7

関数をまったく実行しない (NOOP) のはどうですか? または固定値を使用します。それは重要ですか？

于 2009-05-25T08:10:03.913 に答える
7

この質問を読んで、会話の内容を理解したい人にとっては、これが役立つかもしれません:

|    |constant |logarithmic |linear|  N-log-N |quadratic|  cubic  |  exponential  |
|  n |  O(1)   | O(log n)   | O(n) |O(n log n)|  O(n^2) |  O(n^3) |     O(2^n)    |
|  1 |       1 |          1 |     1|         1|        1|       1 |             2 |
|  2 |       1 |          1 |     2|         2|        4|       8 |             4 |
|  4 |       1 |          2 |     4|         8|       16|      64 |            16 |
|  8 |       1 |          3 |     8|        24|       64|     512 |           256 |
| 16 |       1 |          4 |    16|        64|      256|   4,096 |         65536 |
| 32 |       1 |          5 |    32|       160|    1,024|  32,768 | 4,294,967,296 |
| 64 |       1 |          6 |    64|       384|    4,069| 262,144 |   1.8 x 10^19 |
于 2016-04-30T01:57:23.537 に答える
7

私はよく O(1/n) を使用して、入力が大きくなるにつれて小さくなる確率を表します。たとえば、公正なコインが log2(n) 回の反転で裏になる確率は O(1/n) です。

于 2009-05-25T17:52:18.063 に答える
6

O(1) は単に「一定時間」を意味します。

loop[1] に早期終了を追加すると、(big-O 表記で) O(1) アルゴリズムが O(n) に変わりますが、高速になります。

秘訣は、一般に定数時間アルゴリズムが最適であり、指数アルゴリズムよりも線形アルゴリズムの方が優れていることですが、n の量が少ない場合は、指数アルゴリズムの方が実際には高速である可能性があります。

1: この例では静的なリストの長さを想定しています

于 2009-05-25T12:28:45.170 に答える
4

多くの人が正しい答えを持っています (いいえ) それを証明する別の方法があります: 関数を持つためには、関数を呼び出す必要があり、答えを返さなければなりません。これには一定の時間がかかります。入力が大きいほど残りの処理にかかった時間が短くなったとしても、答えの出力 (これは 1 ビットであると想定できます) には、少なくとも一定の時間がかかります。

于 2010-07-09T19:29:46.037 に答える
3

量子アルゴリズムは、重ね合わせを介して「一度に」複数の計算を実行できると信じています...

これが有用な答えであるとは思えません。

于 2009-05-25T06:20:14.763 に答える
2

O(1) を下回ることはできませんが、k が N より小さい O(k) は可能です。私たちはそれらを準線形時間アルゴリズムと呼びました。一部の問題では、サブリニア時間アルゴリズムは特定の問題に対して近似解しか提供できません。ただし、おそらくデータセットが大きすぎるか、すべてを計算するには計算コストが高すぎるため、近似解で問題ない場合があります。

于 2009-05-25T06:51:32.777 に答える
1

残りの回答のほとんどは、big-O をアルゴリズムの実行時間だけに限定していると解釈しています。しかし、質問では言及されていなかったので、数値解析におけるbig-Oの他のアプリケーション、つまりエラーについて言及する価値があると思いました。

多くのアルゴリズムは、ステップ サイズ (h) と分割数 (n) のどちらについて話しているかに応じて、O(h^p) または O(n^{-p}) になります。たとえば、オイラー法では、y(0) と dy/dx (y の導関数) がわかっている場合、y(h) の推定値を探します。y(h) の推定値は、h が 0 に近いほど正確になります。したがって、任意の x の y(x) を見つけるには、間隔 0 から x を取り、それを n 個まで分割し、オイラー法を実行します。各ポイントで、y(0) から y(x/n) から y(2x/n) などを取得します。

そのため、オイラー法は O(h) または O(1/n) アルゴリズムになります。ここで、h は通常ステップ サイズとして解釈され、n は間隔を分割する回数として解釈されます。

浮動小数点の丸め誤差のため、実際の数値解析アプリケーションでは O(1/h) を持つこともできます。間隔を短くすると、特定のアルゴリズムの実装でより多くのキャンセルが発生し、有効桁数が失われるため、アルゴリズムを介して伝播されるエラーが増加します。

オイラー法では、浮動小数点を使用している場合は、十分に小さなステップとキャンセルを使用し、小さな数を大きな数に追加して、大きな数を変更しません。2 つの非常に近い位置で評価された関数から 2 つの数値を減算して導関数を計算するアルゴリズムの場合、滑らかな関数 y で (y(x+h) - y(x) / h) で y'(x) を近似します。 (x+h) は y(x) に近づくため、相殺が大きくなり、導関数の推定の有効数字が少なくなります。これは、導関数が必要なアルゴリズム (境界値問題など) に伝播します。

于 2017-07-30T02:07:18.087 に答える
1

O（1）未満は不可能だと思います。アルゴリズムにかかる時間は O(1) と呼ばれます。しかし、O(1/n) の場合、以下の関数はどうでしょうか。（このソリューションにはすでに多くのバリアントが提示されていることは知っていますが、それらにはすべていくつかの欠陥があると思います（重大ではなく、概念をよく説明しています）。議論のために、ここに1つを示します。

def 1_by_n(n, C = 10):   #n could be float. C could be any positive number
  if n <= 0.0:           #If input is actually 0, infinite loop.
    while True:
      sleep(1)           #or pass
    return               #This line is not needed and is unreachable
  delta = 0.0001
  itr = delta
  while delta < C/n:
    itr += delta

したがって、n が増加するにつれて、関数にかかる時間はますます短くなります。また、入力が実際に 0 の場合、関数が戻るまでに時間がかかることも保証されています。

機械の精度によって制限されると主張する人もいるかもしれません。したがって、 eit には上限があるため、O(1) です。しかし、文字列で n と C の入力を取得することで、それをバイパスすることもできます。また、文字列に対して加算と比較が行われます。アイデアは、これで n を任意に小さく減らすことができるということです。したがって、n = 0 を無視しても、関数の上限は制限されません。

また、実行時間が O(1/n) であるとは言えません。しかし、O(1 + 1/n) のように言う必要があります。

于 2019-01-27T01:21:06.370 に答える
1

指摘されているように、null 関数の例外の可能性を除けばO(1/n)、かかる時間が 0 に近づく必要があるため、関数が存在しない可能性があります。

もちろん、Konrad によって定義されたようなアルゴリズムはいくつかありますが、O(1)少なくともある意味でそれよりも小さくする必要があるようです。

def get_faster(list):
    how_long = 1/len(list)
    sleep(how_long)

これらのアルゴリズムを調査したい場合は、独自の漸近的な測定値を定義するか、独自の時間の概念を定義する必要があります。たとえば、上記のアルゴリズムでは、一定回数の「無料」操作の使用を許可できます。上記のアルゴリズムで、睡眠以外のすべての時間を除外して t' を定義すると、t'=1/n、つまり O(1/n) になります。漸近的な動作は自明なので、おそらくもっと良い例があります。実際、自明ではない結果をもたらす感覚を誰かが思いつくことができると確信しています。

于 2010-07-09T11:19:32.083 に答える
0

確かに上限まで O(1/n) であるアルゴリズムが表示されます。

ルーチンの外部の何かによって変化する大量の入力があり (おそらく、それらはハードウェアを反映しているか、それを実行しているプロセッサ内の他のコアである可能性さえあります)、ランダムではあるが有効なものを選択する必要があります。

変更されていない場合は、単純にアイテムのリストを作成し、ランダムに 1 つを選択して O(1) 時間を取得します。ただし、データの動的な性質により、リストを作成することはできません。単純にランダムにプローブして、プローブの有効性をテストする必要があります。(そして、本質的に、返されたときに回答がまだ有効であるという保証はないことに注意してください。これには、ゲーム内のユニットの AI など、用途がある可能性があります。トリガーを引く。）

最悪の場合のパフォーマンスは無限大ですが、平均的なケースのパフォーマンスはデータ領域がいっぱいになるにつれて低下します。

于 2009-05-28T00:36:35.470 に答える
0

数値解析では、近似アルゴリズムは、近似許容誤差の漸近的複雑度が準定数になる必要があります。

class Function
{
    public double[] ApproximateSolution(double tolerance)
    {
        // if this isn't sub-constant on the parameter, it's rather useless
    }
}
于 2010-01-24T00:12:54.050 に答える
-1

O(1/n) のアルゴリズムを構築できる可能性があります。1 つの例は、f(n)-n の倍数を反復するループです。ここで、f(n) は、値が n より大きいことが保証されている関数であり、n が無限大に近づくときの f(n)-n の制限は次のとおりです。ゼロ。f(n) の計算も、すべての n に対して一定である必要があります。f(n) がどのように見えるか、またはそのようなアルゴリズムがどのような用途に使用されるかはわかりませんが、私の意見では、そのような関数は存在する可能性がありますが、結果のアルゴリズムには、アルゴリズムの可能性を証明する以外の目的はありません。 O(1/n)。

于 2011-04-29T23:08:34.047 に答える
-2

入力データに関係なく答えが同じ場合は、O(0) アルゴリズムを使用しています。

つまり、入力データが送信される前に答えがわかっている - 関数が最適化される可能性がある - したがって、O(0)

于 2009-05-25T08:15:13.043 に答える
-2

Big-O 表記は、アルゴリズムの最悪のシナリオを表しており、通常の実行時間とは異なります。O(1/n) アルゴリズムが O(1) アルゴリズムであることを証明するのは簡単です。定義により、
O(1/n) --> T(n) <= 1/n、すべての n >= C > 0
O(1/n) --> T(n) <= 1/C であるため、すべての n >=C に対して 1/n <= 1/C
O(1/n) --> O(1)、Big-O 表記は定数を無視するため (つまり、C の値は重要ではない)

于 2009-05-25T13:18:41.777 に答える
-2

これは単純な O(1/n) アルゴリズムです。そして、それは何か面白いことさえします！

function foo(list input) {
  int m;
  double output;

  m = (1/ input.size) * max_value;  
  output = 0;
  for (int i = 0; i < m; i++)
    output+= random(0,1);

  return output;
}

入力のサイズが大きくなると関数の出力がどのように変化するかを説明するため、O(1/n) が可能です。関数 1/n を使用して関数が実行する命令の数を記述する場合、関数が任意の入力サイズに対してゼロ命令を取る必要はありません。むしろ、すべての入力サイズに対して、あるしきい値を超える n に対して、必要な命令の数は、1/n を掛けた正の定数によって制限されます。1/n が 0 になる実際の数はなく、定数は正であるため、関数が 0 以下の命令を取るように制約される理由はありません。

于 2009-09-15T22:43:43.433 に答える
-2

アルゴリズムについてはわかりませんが、ランダム化されたアルゴリズムには O(1) 未満の複雑さが現れます。実際、o(1) (小さい o) は O(1) よりも小さいです。この種の複雑さは通常、ランダム化されたアルゴリズムで発生します。たとえば、あなたが言ったように、あるイベントの確率が 1/n のオーダーの場合、o(1) で表します。または、何かが高い確率で発生すると言いたい場合 (例: 1 - 1/n)、1 - o(1) で表します。

于 2016-04-24T19:15:15.400 に答える
-2 
inline void O0Algorithm() {}
于 2009-08-17T09:50:06.637 に答える
-2

O(1) よりも小さいものはありません Big-O 表記は、アルゴリズムの複雑さの最大オーダーを意味します

アルゴリズムのランタイムが n^3 + n^2 + n + 5 の場合、それは O(n^3) です n -> Inf として、n^2 はn^3

n -> Inf と同様に、O(1/n) は O(1) と比較して無関係になるため、3 + O(1/n) は O(1) と同じになり、O(1) は可能な限り最小の計算になります。複雑

于 2009-05-28T00:08:51.877 に答える
-3

サブリニアアルゴリズムがあります。実際、Bayer-Moore 探索アルゴリズムはその非常に良い例です。

于 2010-01-24T00:23:30.420 に答える
-3

数学はわかりませんが、概念は、入力を追加するほど時間がかからない関数を探しているように見えますか? その場合はどうですか：

def f( *args ): 
  if len(args)<1:
    args[1] = 10

この関数は、オプションの 2 番目の引数を追加するとより高速になります。これは方程式ではないことはわかっていますが、ウィキペディアのページには、big-O はコンピューティング システムにも適用されることが多いと書かれています。

于 2009-05-25T08:24:35.180 に答える