시간 순서와의 반복 관계에서 얻는 방법

Question

그래서 저는 quicksort에 대한 reccurence 관계를 조사해 왔습니다. 그리고 나는 그들이 최종 반복 관계에 도달하는 방법을 따를 수 있지만 시간 순서대로 점프합니다. 예를 들면 :

최악의 경우 : 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의 순서가 올됩니다.