如何解决重现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是免费的(O(nlog(n!))).如果你正在寻找一个大the,你需要再努力一点.