본문 바로가기

# Foundation/기초수학

급수 알고리즘

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

급수(Series)의 정의

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


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

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


급수 알고리즘 개요 

사실 알고리즘도 아니다.

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


Function Information

 series_arth(a0, d, n)

 순회를 이용하여 산술급수를 구한다.

 series_arth_formla(a0, d, n)

 급수공식을 이용하여 산술급수를 구한다.

 series_geo(a0, r, n)

 순회를 이용하여 기하급수를 구한다.

 series_geo_formla(a0, r, n)

 급수공식을이용하여 기하급수를 구한다.

 series_exp2(n)

 순회를 이용하여 지수가 2인 지수급수를 구한다.

 series_exp2_formla(n)

 급수공식을 이용하여 지수가 2인 지수급수를 구한다.

 series_exp3(n) 순회를 이용하여 지수가 3인 지수급수를 구한다.
 series_exp3_formla(n) 급수공식을 이용하여 지수가 3인 지수급수를 구한다.


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 + ...)


유한급수의 성질과 공식

<성질>

<공식>

  • 산술 급수 : 등차 수열의 급수 (Arithmetic Series)


  • 기하 급수 : 등비 수열의 급수 (Geometric series)


  • 지수 급수 : 지수 수열의 급수 (Exponential Series)


1. 산술급수 

<핵심>

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

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



2. 기하급수

<핵심>

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

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



3. 지수급수

<핵심>

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

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





'# Foundation > 기초수학' 카테고리의 다른 글

파도반 수열 알고리즘  (0) 2018.11.04
피보나치 수열 알고리즘  (0) 2018.11.03
소수 알고리즘  (0) 2018.10.26
최대 공약수와 최소 공배수의 관계  (0) 2018.10.24
최소 공배수 알고리즘  (0) 2018.10.23