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를 사용합니다.

내가 그것을 상한을 제공했다 경우 나는 다음과 같은 시도 제안 :

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!))). 당신이 big-theta을 찾고 있다면, 좀 더 고생 할 필요가 있습니다.

Answer 2

1. A (0) = c라고합시다. sum으로 정의되는 n과 c의 함수로 A (n)을 찾습니다.
2. 얼마나 많은 용어가 합계에 있습니까?
3. 합계의 최소값은 얼마입니까? 견적을 찾아보십시오.
4. 합계의 최대 값은 얼마입니까? 견적을 찾아보십시오.
5. (3)과 (4) 중 하나가 다른 것보다 일정한 시간이 길어질 수 있다고 추정 할 수 있다면 끝났습니까? 왜?