자료구조를 위한 수학

기본적인 함수

1. 마루(Floor)와 천장(Ceil) 함수

- 마루 함수

어떤 실수 x 이하인 제일 큰 정수를 반환

ex)

3.2 = 3

-5.2 = -6

 

- 천장 함수

어떤 실수 x 이상인 제일 작은 정수를 반환

ex)

3.2 = 4

-5.2 = -5

 

2. 로그 함수

- f(n) = n½ = √n는 In(n)보다 항상 크다

 

- 로그와 지수 함수의 증가율 비교

  o 지수 함수는 d > 0에서 그 어떤 비상수 다항식보다 빠르게 증가한다.

  o 그러므로 지수 함수의 역함수인 로그 함수는 그 어떤 다항식보다 느리게 증가한다.

ex) f(n) = n½ = ²√n는 In(n)보다 항상 빠르게 증가한다.

 

ex) f(n) = n⅓ = ³√n은 n = 93까지만 In(n)보다 느리게 증가한다.

- 로그 함수의 표기, 종류, 구현

  o 밑수 2 로그함수는 log2(n)이고, lb(b) 또는 lg(n)으로 표시할 수 있음.

  o 자연로그 in(n)은 표준적으로 다움과 같이 구현 : double log(double);

  o 상용 로그 함수 log10(n)은 다음과 같이 구현 : double log10(double);

 

- 로그 함수의 교환 정리 및 증명

  o 로그 함수 작성 예시 : nlogb(m) = mlogb(n)

 

- 로그 함수 계산의 예

lg(2의 10승) = lg(1024) = 10

lg(2의 20승) = lg(1024) = 20

 

급수와 재귀 함수

1. 급수 - 수열의 합

- 산술 급수

  o 각 항의 상수 값만큼 증가

초기값 k부터 n값까지의 합

ex) n = 100이면, 100 * 101 / 2 = 5050이라는 결과 값

- 기타 급수

  o 공식 일반화

 

  o 정적분의 근사합 : 그래프의 어떤 영역을 연속적으로 구하는 공식

  o 실제값과 근사값의 비는 n → ∞ 일 때 1로 수렴

"결론적으로 상대 오차는 0"

 

- 기하 급수

  o 기하 급수는 상수값의 비율로 증감함

 

2. 재귀 함수

  o 기하 함수의 정의 시 자기 자신을 다시 호출하는 함수

N! = 1 (When N=0)

      N*(N-1)! (Otherwise)

 

ex)

3! = 3 * 2!

   = 3 * 2 * 1!

   = 3 * 2 * 1 * 0!

   = 3 * 2 * 1 * 1!

   = 3 * 2 * 1 = 6

 

- 재귀 함수의 활용

  o 두 재귀적 함수들에 대하여

  o 비재귀적으로 변환 필요

 

가중 평균 및 조합

1. 가중 평균

- 가중 평균(Weighted Averages)

  o n개의 개체에 각각 서로 다른 가중치를 곱하여 평균을 낸 것

  o 모든 가중치의 합은 1이 되어야 함

 

1. 조합

- 조합(Combination)이란?

  o 주어진 서로 다른 n개의 개체에서 k개를 선택하는 방법의 가지 수

  o 순서는 관계가 없음

 

- 조합의 예시

ex) 집합 {1, 2, 3, 4, 5}에서 3개의 원소를 선택하는 방법은?

함수 표현법으로 표기

※ n =5, k = 3, !은 팩토리얼

 

ex) n이 k를 선택한다고 읽고, 다음과 같이 재귀적으로 정의할 수 있음

 

- 조합의 활용

  o 다항식의 계수를 다음과 같이 계산할 수 있음

ex) n = 4