math - 「ln ln n / ln 2 + O(1)」の O(1) とはどういう意味ですか?

Question

この式の O(1) 表記がわかりにくいのですが、これは定数を表していますか? なぜ人々はこのように big-O 記法を使うのでしょうか?

この式は、 Azar らによる論文「Balanced Allocations」に由来します。、およびこの式は要約で使用されます。

Answer 1

はい、O(1)定数を意味します。定数の正確な値は指定されていませんが、指定された式ではおそらく重要ではありません。このような概念は通常、計算の中間ステップとして使用され、重要でない詳細の計算を削除します。

この式を次のように読んでくださいlnlnn/ln2。定数の追加により、実行に時間がかかります。これをまとめると、 になりますO(lnlnn)。正確な式に置き換えO(1)てもこの結果は変わらないので、 の形で近似を使用しても問題ありませんO(1)。