n log nはO（n）ですか？

Question

この再発を解決しようとしています

T（n）= 3 T（n / 2）+ n lg n ..

n lg nはO（n ^ 2）であるため、マスター定理のケース2に属するという解決策に到達しました

しかし、ソリューションマニュアルを参照した後、私は彼らが持っているこのソリューションに気づきました

このソリューションでは、eが0から0.58の場合、n lg n= O（n ^（lg 3-e））と表示されます

つまり、n lg nはO（n）です..これは正しいですか？ここで何かが足りませんか？

nlgn O（n ^ 2）ではありませんか？

Answer 1

これは物事をよりよく説明します

Answer 2

n*log(n)はO(n^2)ではありません。これは準線形として知られており、O(n^2)よりもはるかにゆっくりと成長します。実際、n*log(n)は多項式よりも小さいです。

言い換えれば： ジェネラコディセタグプレ

ここでk > 1

あなたの例では： ジェネラコディセタグプレ

O(n^1.585)は多項式であり、O(n*log(n))を支配するため、後者の用語は削除され、最終的な複雑さはO(n^1.585)になります。

Answer 3

n ^{lg3 はO（n）ではありません。それはO（n）を超えます...実際、1より大きいnの指数は、O（n）よりも漸近的に長い時間をもたらします。lg（3）は約1.58なので、指数から.58未満を引く限り、O（n）よりも漸近的に大きくなります。}