私のロジックを検証して、私が試みていることが有効かどうかを確認してください。
W(n) = W(n/2) + nlg(n)
W(1) = 1
n =2^k
パターンを試すことで
line 1 : W (2^k) = W(2^k-1) + nlgn
line 2 : = W(2^k-2) + nlgn + nlgn
...
line i : = W(2^k-i) + i*nlgn
そして残りを i について解きます。
1 つの場所 (1 行目)で 2 kを置き換え、他の場所ではn lg n
.
2^k for 2^k lg(2^k)
下塗りすると本当に脂っこくなることがわかりました。
任意の考えを歓迎します (具体的には、2^k に潜入する必要がある場合、およびそうする必要がある場合は、どのように解決策を提案しますか)