私は現在、アルゴリズムクラスで大きなO表記法を学んでいます。私はこの問題を私に戸惑わせました。正式な定義が成り立つことがわかっていれば、O（n lg（n））をc * n * lg nとして表すことができますか？意味は、f（n）< = c n lg nであり、定義がいくつかの定数について真である場合、O（n lg n）は、c * n * lg n？そして、私の仮定が真であるならば、我々は行うことができます：ログ（O（n * log（n）））は何ですか？
= LG（O（n個のLG N））
= LG（C×n個* LG n）で
= LG（C）+ lg（n）がこの場合の最上位の項である場合、これはO（lg（n））と単純化されますか？lg（n）+ lgすべての下位項は最終的に最高次項と重複するので、
はい、あなたは正しく、あなたの数学は正しいです。
あなたの質問は従うことが少し難しいです。私はあなたが求めていると思う：
は、私たちが
O(n lg n)の割合以下で漸近的に成長する機能fがあるとします。関数lg ∘ fは、O(lg n)の速度以下で漸近的に成長するか？
はい、あります。
UPDATE：Commenter Paul Hankinは反例を指摘しています。おそらく、これは正しいですか？
ちょうど
O(n lg n)の割合で漸近的に成長する関数fがあるとします。関数lg ∘ fは、O(lg n)の割合で漸近的に成長するか？
私はその答えは「はい」だと思います。
exp（-n）= O（n lg n）。しかし、lg（exp（-n））= -nはO（lg n）ではありません。 –
@PaulHankin：ええと、反例です。 Vexing！アルゴリズムのコストが負の線形*に成長することは、何を意味するのか疑問に思います。 –
私はfにいくつかの制限が必要であると思っています。 f = Theta（n lg n）、またはf> = 1のいずれかの仕事をすると思います。 –
これは、lg(O(n lg n)) = O(lg n)を表示しようとしています。これはやや標準的ではない表記ですが、fがO(n lg n)の場合、gはO(lg n)になり、log(f) = gとなります。これはウィキペディアでここに説明されています：https://en.wikipedia.org/wiki/Big_O_notation#Multiple_usages
この文は、書かれているとおり、まったく真実ではありません。たとえば、f = 2^(-n)はO(n lg n)にありますが、lg(f) = -nはO(lg n)にはありません。しかし、自分自身を1よりも大きいfに制限すれば、それは当てはまります。
f = O(n lg n)の場合は、すべてが十分に大きいn、f(n) < cn lg nとなるようなcがあります。その後、lg(f(n)) < lg(c) + lg(n) + lg(lg(n)) = O(lg n)。 lg(f(n)) > 0以降、私たちはそれを持っていますlg(f(n)) = O(lg n)。これは本質的に、定義について少し注意を払い、lg(f(n))が大きくて否定的でないことを確認しながら、質問からのあなたの証明です。
'n'は任意に大きくなるので、' nlgn'項は定数n回のように動作するので、 'lg（c * n）'のままになります。だから私はあなたの推論が正しいと思います。 –
あなたが提起した問題は本質的にナンセンスです。 g（n）= O（f（n））は、gの成長の速さに関するアサーションです。 O（。）は関数ではありません。したがって、log（O（。））は迷惑です。 – Gene
@Gene：なぜOは関数ではないと思いますか？関数の定義とは何ですか？ –