개발자를 위한 수학 Day2

1.확률과 통계 (기댓값 - 알고리즘 분석)

 

컴퓨터 알고리즘 분석에서, 정렬 알고리즘의 평균 시간 복잡도를 구할 때
기댓값(Expectation)을 자주 사용한다.

어떤 정렬 알고리즘에서 배열의 크기가 $ n $ 일 때,
비교 연산의 기대 횟수 $ E(X) $ 가 다음과 같이 주어진다고 하자.

$$
E(X) = \sum_{k=1}^{n} \frac{n}{k}
$$

이 기댓값을 조화급수(Harmonic Series) $ H_n $ 를 이용해 근사하면,
$$
E(X) \approx O(?)
$$

여기서 빅오 표기법으로 기대 연산 횟수를 나타내시오.

 

 

 

2.해석학 (수열의 수렴 - 머신러닝 관련)

머신러닝에서 손실 함수의 수렴 분석을 할 때,
다음과 같은 점화식으로 표현된 수열이 자주 등장한다.

어떤 수열 $ a_n $ 이 다음과 같이 정의된다고 하자.

$$
a_{n+1} = \frac{1}{2} a_n
$$

초기값이 $ a_1 = 8 $ 일 때,
$ a_n $ 의 일반항(Explicit Formula) $ a_n $ 을 구하고,
이 수열이 어떤 값에 수렴하는지 판별하시오.

 

풀이

---

 

 

1.확률과 통계 (기댓값 - 알고리즘 분석)

 

컴퓨터 알고리즘 분석에서, 정렬 알고리즘의 평균 시간 복잡도를 구할 때 기댓값을 자주 사용해.

주어진 기대 연산 횟수:
$$
E(X) = \sum_{k=1}^{n} \frac{n}{k}
$$

여기서 ( n ) 은 상수이므로 앞으로 빼주면:
$$
E(X) = n \sum_{k=1}^{n} \frac{1}{k}
$$

이때, 조화급수(Harmonic Series) ( H_n ) 를 이용하면:
$$
H_n = \sum_{k=1}^{n} \frac{1}{k} \approx \ln n
$$

따라서 기대 연산 횟수는:
$$
E(X) \approx n \ln n
$$

즉, 빅오 표기법으로는 ( O($ n \ln n $) ) 이다.

 

 

2.해석학 (수열의 수렴 - 머신러닝 관련)

 

주어진 점화식:
$$
a_{n+1} = \frac{1}{2} a_n
$$

초기값이 ( a_1 = 8 ) 일 때, 이를 일반항으로 변환해보자.

 

1. 일반항 구하기

반복적으로 대입하면:
$$
a_2 = \frac{1}{2} a_1 = \frac{1}{2} \times 8 = 4
$$
$$
a_3 = \frac{1}{2} a_2 = \frac{1}{2} \times 4 = 2
$$
$$
a_4 = \frac{1}{2} a_3 = \frac{1}{2} \times 2 = 1
$$

패턴을 보면:
$$
a_n = 8 \times \left(\frac{1}{2}\right)^{n-1}
$$

즉, 일반항은:
$$
a_n = 8 \times 2^{-(n-1)}
$$

 

2. 수렴 여부 판단

$$
\lim_{n \to \infty} 8 \times 2^{-(n-1)} = 0
$$

즉, 이 수열은 0에 수렴한다!