Bogosort の動作に上限を設けることはできないと聞いたことがあります。ただし、その平均的な動作について誰かが話しているのを聞いたことがありません。それはばかげた作業ですが、非現実的な思考実験は、たとえ非現実的であっても、良い実践として役立ちます。
各用語は次のとおりです。
P(x==y)*P(x!=y)^(k-1)
= 1/n * (1-1/n)^(k-1)
= (n-1)^(k-1) / n^k
ここで、k は 0 以上です。私はその級数が収束することを知っているので、複雑さの有限対有限の関係を見つけることができます (他の人が限界を設定しようとしてフラストレーションから O(無限大) と書こうとした最悪の場合の動作とは異なります)。無限の機能。)
誰でもこれを解決できますか？それとも、無限和なしでは記述または近似できない複雑さですか?