급수 알고리즘

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
    https://github.com/AeroCodeX/

급수(Series)의 정의

수열 An이 주어졌을 때, 수열(Sequence)에 속해있는 모든 원소의 합.

끝이 존재하는 수열의 급수를 유한급수라고 하며,

끝이 존재하지 않는 수열의 급수를 무한급수라고 한다.

급수 알고리즘 개요

사실 알고리즘도 아니다.

급수 공식을 활용하면 대부분 상수 시간내에 수열의 합을 계산할 수 있다.

Function Information

RunningTime Statistics (1,000,000회 평균값)

n up to	10^1	10^2	10^3	10^4	Time	Memory
`series_arth()`	0.06 μs	0.36 μs	2.82 μs	26.63 μs	n	1
`series_arth_formla()`	0.04 μs	0.04 μs	0.04 μs	0.04 μs	1	1
`series_geo()`	0.08 μs	0.57 μs	5.03 μs	48.65 μs	n	1
`series_geo_formla()`	0.08 μs	0.56 μs	4.17 μs	42.90 μs	n	1
`series_exp2()`	0.07 μs	0.35 μs	3.16 μs	28.66 μs	n	1
`series_exp2_formla()`	0.03 μs	0.03 μs	0.03 μs	overflow	1	1
`series_exp3()`	0.05 μs	0.31 μs	2.51 μs	overflow	n	1
`series_exp3_formla()`	0.02 μs	0.02 μs	0.02 μs	0.02 μs	1	1

* 프로파일링에 사용된 수열

산술수열 : a0=0이고, d=1인 등차수열

기하수열 : a0=0이고, r=2인 등비수열

지수수열 : a0=1인 지수수열 (1^2 + 2^2+ 3^2 + ...)

유한급수의 성질과 공식

<성질>

<공식>

1. 산술급수

<핵심>

1. 산술급수란 산술수열(등차수열)의 급수이다.

2. 산술급수의 공식은 상수 시간에 끝낼 수 있다.

2. 기하급수

<핵심>

1. 기하급수란 기하수열(등비수열)의 급수이다.

2. 기하급수의 공식에는 지수가 포함되어 있으므로 n 시간에 끝난다.

3. 지수급수

<핵심>

1. 지수급수란 지수수열의 급수이다.

2. 지수급수의 공식은 상수 시간에 끝낼 수 있다.

AeroCode;