私はこの再発を解決しようとしています
T(n) = 3 T(n/2) + n lg n ..
n lg n は O(n^2) であるため、マスターの定理ケース 2 に属するという解決策にたどり着きました。
しかし、ソリューションマニュアルを参照した後、彼らが持っているこのソリューションに気づきました
解は、0 から 0.58 の間の e に対して 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)、 は多項式よりも小さいです。
言い換えると：
O(n*log(n)) < O(n^k)
どこk > 1
あなたの例では：
3*T(2n) -> O(n^1.585)
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) よりも漸近的に大きくなります。