最悪の複雑さが入力サイズに反比例するアルゴリズム？

Question

可能性の重複：
Are there any O(1/n) algorithms?

複雑入力サイズの増加に伴って減少する任意のアルゴリズム？

私は最悪の場合のパフォーマンスについて話しています。

一般に、入力サイズとともに大きさが減少する数学グラフは知っていますが、これらのグラフに一致する有意義なアルゴを持っていますか？

Answer 1

これはいかがですか？

Mystery(array[1..n]) 
1. x := fn(0) 
2. for i = 1 to floor(1,000,000/n) do 
3. x = fn(x) 
4. return x 

すべてのこのようなアルゴリズムは、明白な理由から、漸近的に言えば、一定時間である。

EDIT：整数の除算は、私はそれがあると信じている、対数である場合

は実際には、これは、漸近的にO（ログn）です。 http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operationsこのように、私の答えは実際にはO（1/n）アルゴリズムはないということです。 O（1）は最小の複雑さクラスです...計算することなくその入力サイズの逆数を知るアルゴリズムを作る方法がない限り！

EDIT2：

私はおそらく入力として関数に1,000,000/n個を渡すと思った...しかし、アルゴリズムがその条件に違反した場合は指示する方法はありませんので、それは、実際に本物の解決策ではありません、とにかくそれを計算する必要があります。算術演算を一定の時間にするのであれば、固定サイズの組み込み型のコンピュータと定義されたレジスタサイズで動作する命令セットを使用していると確信しているので、この議論の多くは特に重要ではありません。

f(Collection c, query q): 
    if q in c: 
    do something fast! 
    else: 
    compute Ackermann function! 

f*(Array a, int i): 
    if a[i] == i: //Or some other condition that takes constant time to verify, 
       //assume i is within bounds 
    do something fast! 
    else: 
    compute Ackermann function! 

まあのような

Answer 2

何かが、当然のことながら、これの性能は、[i]は==私その確率に依存しています。私は徹底的な分析をしていませんが、この確率を計算するためには、配列の性質とf *がどのように呼び出されるかについていくつかの形式の仮定が必要です。

これは面白いことですが、実際にこのシナリオに遭遇するケースは想像できません。

編集：元の回答はfですが、haroldのコメントに対応するためにf *に変更しました。 f *の後で私は私の場合を休んで、ちょうど潜んでいるでしょう。