アルゴリズムがどのように成長するかを考慮して、nlognとlognの違いは何ですか

アルゴリズムがどのように成長するかを理解するためには問題があります。私はO表記法の違いを理解できません。そして私はそれらの間の違いを理解していません（例えば、O（lgn）とO（nlgn））。

私は誰でも助けてくれることを願っています。ありがとうございます

[This]（http://bigocheatsheet.com/）はかなりうまくいきます。 – ChiefTwoPencils

ありがとう@ChiefTwoPencils :)しかし、あなたはなぜあなたの言葉で私を説明することができますnlgnはlgnより悪いですか？それは簡単かもしれませんが、私はそれを非常にはっきりと理解できません。 – flowers1234

まあ、それは本当に数学です。例えば、n = 8、lgn = 3、nlgn = 24の場合。 – ChiefTwoPencils

時間の複雑さを比較するには、数学的な証明を行うことができます。あなたの例：

私はlogn：nlogn> lognを掛け合わせることで、nlognはlognよりも悪くなります。これを理解する簡単な方法は、コメントに示唆されているような関数のグラフを比較すること、または漸近的な振る舞いを見るためにいくつかの大きな入力を試みることです。たとえば、n = 1000000の場合：

logn（1000000）= 6および1000000log（1000000）= 6000000の方が大きい。

また、例えば、4nがO（n）であり、nがO（n）であり、c、w定数でcn + wがO（n）であるなど、大きなO表記でカウント定数を取ります。

2016-10-18 18:02:58 coder

okありがとうございます！ @code – flowers1234

okこれは、例えば、ヒープソートやクイックソートがnlgnの場合、lognを使ったバイナリ検索より速いことを意味します。 – flowers1234

反対ではなく、アルゴリズムが別のアルゴリズムより高速であることを伝えるには、最初のものが2番目のアルゴリズムよりも複雑さが低いことを示す必要があります。私たちがlogn coder

答えて