A (n) = A (n-1) + n * log (n)?

-1

재발이 주어진 경우 :
A(n) = A(n-1) + n*log(n).
A(n)의 시간 복잡도는 어떻게 알 수 있습니까?A (n) = A (n-1) + n * log (n)?

2016-11-07 Shantanu

이 반복 관계가 어떻게 종료되는지 알 수 없습니다. –

@LukaRahne : 참으로. 아마도 A (1)이 첫 번째 용어입니다. – Bathsheba

@Shantanu가 내 문제를 해결 했습니까? 어떻게 든 대답 할 수 있니? 필요한 경우 더 자세한 설명을 드리겠습니다. – xenteros

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을 찾고 있다면, 좀 더 고생 할 필요가 있습니다.

출처

2016-11-07 11:34:51 xenteros

그래서 A (n) = n! • 로그 (n!)가 정확합니까? – ToxiCore

아니, 그렇지 않습니다. 그것은 합계입니다. – xenteros

질문은 반복 결과를 계산하기위한 복잡성이 아니라 결과가 무엇인지에 관한 것입니다. –

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

출처

2016-11-07 11:37:14 user31264

A (n) = A (n-1) + n * log (n)?

답변

관련 문제