[解決済み] O(1/n)のアルゴリズムはあるのか？

質問

O(1/n)のアルゴリズムはあるか？

またはO(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)ですが。それでも面白いんですよ。例えば、非常に単純なテキスト検索アルゴリズムを例にとると ホースプール . ここで、検索パターンの長さが長くなると期待される実行時間は減少する（ただし、干し草の山の長さが長くなると再び実行時間は増加する）。