O(1/n) アルゴリズムはありますか?
あるいはO(1)未満の何か他のものでしょうか?
ベストアンサー1
この質問は、一部の人が思うほど馬鹿げたものではありません。少なくとも理論的には、O (1/ n )のような値は、ビッグオー表記:
これで、 g ( x ) を 1/ xに簡単に置き換えることができます。上記の定義が何らかのfに対して依然として当てはまることは明らかです。
漸近的な実行時間の増加を推定する目的では、これはあまり現実的ではありません…意味のあるアルゴリズムは、入力が増えても高速化することはできません。もちろん、これを満たす任意のアルゴリズムを構築できます。たとえば、次のアルゴリズムです。
def get_faster(list):
how_long = (1 / len(list)) * 100000
sleep(how_long)
明らかに、この関数は入力サイズが大きくなるにつれて、時間が短くなります…少なくとも、ハードウェアによって強制される何らかの制限（数値の精度、sleep待機できる最小時間、引数を処理する時間など）までは。この制限は一定の下限となるため、実際には上記の関数の実行時間は依然としてO (1) です。
しかし、実際には、入力サイズが大きくなると実行時間が（少なくとも部分的に）減少するアルゴリズムがあります。ただし、これらのアルゴリズムはO（1）以下の実行時間では動作しないことに注意してください。それでも、興味深いものです。たとえば、次の非常に単純なテキスト検索アルゴリズムを考えてみましょう。ホースプールここで、検索パターンの長さが長くなるにつれて、予想される実行時間は短くなります (ただし、干し草の山の長さが長くなると、実行時間は再び長くなります)。