algorithm - 関数間の漸近関係は何ですか

Question

与えられた関係に従う理由を知りたい：

1. n < (log n)^log n
2. log log n = O(root(log n))
3. (log n) != omega(log(n!))
4. log(log*n) < log*(log n)

すべてのログのベースは 2 です。明らかに、答えはわかっていますが、それらを見つける方法がわかりません。常に値を入力するだけでは、これらを見つけることができないこともわかりnました。については第1関係は成り立たないn=2。上記の関数を の大きな値に適用すると、どのような効果がありnますか? 上記の（または与えられていない追加機能）関数のさまざまな組み合わせを適用する際の関係を見つけることができるように、誰でも普遍的な解決策を提供できますか（または私に道を案内してくれますか）n。たとえばlog*log(root(log(n!)))、loglog*(log(root(n!)))

Answer 1

大まかに言えば、漸近とは無限に近づくことを意味します (関数がその漸近線に近づくにつれて)。

したがって、大まかな見積もりには、非常に大きな n を使用してください。

より正確な定義と議論については、 Asymptotic Analysisまたはコンピューター サイエンスの入門書を参照してください。