解决大O复发

Question

我有这样的复发：

T（N）= T（N-1）+ O（N log n）的

那么我想解决的办法是T（n）的= O（n log n） 我使用替换方法。

T（n）的< = C *（N-1）*的log（n-1）+ O（N log n）的

T（n）的< = C * N *的log（n）+ O（n log n）= O（n log n）

这是正确的吗？

Answer 1

我认为这是不正确的。我认为这个错误是在最后一步。

我认为正确答案是：T（n）= O（n^2 log n）。

这里的原因：

T（N）= T（N-1）+ O（N log n）的

T（N）= T（N-2）+ O（（正1）log（n-1））+ O（n log n）

T（n）= T（n-3）+ O（（n-2）log（n-2））+ n-1）log（n-1））+ O（n log n）

。

。

。 （n-1）log（n-1））+ O（（n-2）log（n-2））+ ... + O（（N/2）的log（n/2））

T（N）> =（N/2）* O（（N/2）的log（n/2））

Ť （N）> = O（N^2 log n）的

在另一方面：

T（N）= T（N-3）+ O（第（n-2）的log（n-2 ））+ O（（n-1）log（n-1））+ O（n log n）

。

。

。

T（n）的< = N *为O（n log n）的

T（n）的< = O（N^2 log n）的

因此：

T（n）的= O（n^2 log n）