如何从时间顺序的递归关系中获得

Question

因此，我一直在研究快速排序的重新关系关系，我可以按照他们如何得到最终的重现关系，但随后他们跳转到时间顺序。例如：

最坏情况：T（N）= T（N-1）+ CN

然后他们跳转到的时间顺序：为O（n^2）

我不遵循怎样他们从递推关系的时间顺序有...

Answer 1

您可以通过以下方式解决这个问题再次发生： -

T(n)=T(n-1)+cn =T(n-1)+O(n) 
T(n)=T(n-2)+c(n-1)+cn  {bcoz T(n-1)=T(n-2)+c(n-1)} 
T(n)=T(n-3)+c(n-2)+c(n-1)+cn {bcoz T(n-2)=T(n-3)+c(n-2)} 
.  .  . 
.  .  . 
.  .  . 
.  .  . 
T(n)=T(0)+c(1+2+3....+n) 
T(n)=T(0)+c(n(n+1)/2) 
T(n)=T(0)+O(n^2) 

因此它问世的N^2的顺序。