如何求解递归A(n) = A(n-1) + n*log(n)？

Question

鉴于重复：
A(n) = A(n-1) + n*log(n).
如何找到 A(n) 的时间复杂度？

Answer 1

A(n) = A(n-1) + nlog(n)

看，你的递归说：取之前的值并向其添加 nlogn。

所以...假设 A(1) = log(1) 是序列的第一个元素：A(n) = SUM from i = 1 to n (ilog(i)).

为什么？

A(1) = log(1).
A(2) = log(1) + 2log(2).
A(3) = A(2) + 3log(3) = 1log(1) + 2log(2) + 3log(3).
.
.
.
A(n) = 1log(1) + 2log(2) + 3log(3) + ... + nlog(n)

当F(n) - F(n-1)是非递归函数时，总是可以使用这种解决递归的方法。在我们的例子中它是 nlogn 所以它起作用了。

当F(n)/F(n-1) 是非递归函数时，可以使用类似的规则。然后我们用PI代替SIGMA。

如果我被要求给它一个上限，我会建议尝试以下操作：

  log(n)   + log(n)   + log(n)   + log(n)   + ...
+            log(n-1) + log(n-1) + log(n-1) + ...
+                       log(n-2) + log(n-2) + ...
.
.
.

所以

现在你的上界已经很明确了，所以big-o is there for free (O(nlog(n!))). In case you're looking for a big-theta你还需要再挣扎一下。

Answer 2

令A(0)=c。求 A(n) 作为 n 和 c 的函数，由总和定义。
总和有多少项？
总和的最小值是多少？尝试找到一个估计值。
总和的最大值是多少？尝试找到一个估计值。
如果你能估计 (3) 和 (4) 使得其中一个比另一个大常数倍，你完成了吗？为什么？

如何求解递归A(n) = A(n-1) + n*log(n)？

How to solve the recurrence A(n) = A(n-1) + n*log(n)?

algorithm

recurrence

time-complexity

asymptotic-complexity