합 수열 (n^2-1^2) + 2(n^2-2^2) +….n(n^2-n^2)

이 글에서는 (n^2 - 1^2) + 2(n^2 - 2^2) + … n(n^2 -)의 합을 계산하는 다양한 방법을 살펴보겠습니다. n^2). 첫 번째 방법에서는 1~n 범위의 각 i의 시퀀스 합을 하나씩 계산하여 최종 합에 추가합니다.

두 번째 방법에서는 주어진 계열의 합을 계산하는 수학 공식을 유도하여 프로그램의 시간 복잡도를 O(n)에서 O(1)로 줄입니다.

문제 설명 − 숫자 "n"이 주어졌고 우리의 임무는 주어진 수열 (n^2 - 1^2) + 2(n^2 - 2^2) + ...의 합을 계산하는 것입니다. (n^2 - n^2).

예

Input − 숫자 = 5

Output - n = 5일 때 계열의 합(n^2 - 1^2) + 2(n^2 - 2^2) + …. n(n^2 - n^2)은 150입니다. .

Input − 숫자 = 3

Output - n = 3인 경우 계열 (n^2 - 1^2) + 2(n^2 - 2^2) + ….n(n^2 - n^2)의 합은 18입니다. .

방법 1

이것은 시퀀스 합계 문제를 해결하는 가장 간단한 무차별 대입 방법입니다.

이 수열을 주의 깊게 분석한 후 다음과 같은 결론을 내릴 수 있습니다. 임의의 숫자 n에 대해 다음과 같은 결과가 나옵니다.

Sum = ∑ i*(n^2 - i^2) for i = 1 to i = n.

따라서 무차별 방식의 경우 i부터 n까지의 루프에서 위 공식을 사용하여 필요한 합계를 생성할 수 있습니다.

예

이 메서드의 코드는 다음과 같습니다.

으아아아

출력

으아아아

복잡성

시간 복잡도 - 1에서 n까지 루프를 반복할 때 O(n)입니다.

공간 복잡도 - 외부 공간을 사용하지 않으므로 이 방법의 공간 복잡도는 O(1)입니다.

방법 2

이 방법에서는 필요한 시퀀스 합계를 직접 얻는 공식을 유도하므로 반복이 필요하지 않으며 이 방법은 일정한 시간 복잡도로 주어진 문제를 해결합니다.

앞서 언급했듯이

로 제공되는 시리즈의 일반 버전을 얻습니다. 으아아아

같은 시리즈는 다음과 같이 쓸 수 있습니다:

으아아아

우리는 1부터 n까지의 모든 숫자의 합을 계산하는 공식과 1부터 n까지의 모든 숫자의 세제곱의 합을 계산하는 공식을 각각 알고 있습니다.

1부터 n까지의 모든 숫자의 합

으아아아

n은 주어진 숫자입니다.

이제 1부터 n까지 모든 숫자의 세제곱의 합을 구해 보세요

으아아아

그래서 주어진 시리즈는 다음과 같이 쓸 수 있습니다.

으아아아

합은 -

로 더 단순화할 수 있습니다. 으아아아

따라서 원하는 시퀀스의 합을 얻으려면 모든 n에 대해 Sum = (n^4)/4 - (n^2)/4를 계산하면 됩니다.

예

이 메서드의 코드는 다음과 같습니다.

으아아아

출력

으아아아

복잡성

시간 복잡도 - 우리가 도출한 공식을 사용하여 필요한 합계를 계산하기 때문에 O(1)입니다.

공간 복잡도 - 외부 공간을 사용하지 않으므로 이 방법의 공간 복잡도는 O(1)입니다.

결론 - 이 글에서는 필요한 계열의 합을 계산하는 두 가지 방법에 대해 논의했고 두 번째 방법에서는 시간 복잡도를 상수로 줄였습니다.

위 내용은 합 수열 (n^2-1^2) + 2(n^2-2^2) +….n(n^2-n^2)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!