質問
この再発を解決しようとしています
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)ではありませんか?
解決
これは物事をよりよく説明します
他のヒント
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)
になります。
n lg3 はO(n)ではありません。それはO(n)を超えます...実際、1より大きいnの指数は、O(n)よりも漸近的に長い時間をもたらします。lg(3)は約1.58なので、指数から.58未満を引く限り、O(n)よりも漸近的に大きくなります。
所属していません StackOverflow