알고리즘) 기본 수학 이론

1. 알고리즘 복잡도

• 입력 크기의 값에 대해 단위 연산을 몇  번 수행하는지 계산하여, 알고리즘의 수행시간을 평가하는 방법.

 

3가지 점근적 표현법

• O(빅오): 최악의 상황을 고려하여 성능 측정 결과 표현.
• Θ(세타): 평균적인 경우에서의 성능 측정 결과 표현.
• Ω(오메가): 최선의 상황일 때의 성능 측정 결과 표현.

 

 

2. 경우의 수 (순열과 조합)

• 어떤 사건 혹은 일이 일어날 수 있는 경우의 가짓수를 수로 표현
• 완전탐색으로 경우의 수를 푸는 알고리즘
  • 순열: 서로 다른 n 개의 원소 중에서 r를 중복 없이 골라 순서에 상관 있게 나열하는 경우의 수 (nPr)
  • 조합: 서로 다른 n개의 원소 중에서 r를 중복 없이 골라 순서에 상관 없이 나열하는 경우의 수 (nCr)
  • 중복 순열: 서로 다른 n개의 원소 중에서 r개를 중복 있게 골라 순서에 상관 없이 나열하는 경우의 수 (nH)

 

 

3. 점화식(재귀식)

• 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식

 

대표적인 점화식

• 등차 수열: F(n) = F(n - 1) + a   (a:고정된 상수)
• 등비 수열:  F(n) = F(n - 1) * a 
• 팩토리얼:  F(n) = F(n - 1) * n 
• 피보나치 수열:  F(n) = F(n - 1) + F(n - 2)

 

 

 

 

참고

제로베이스 강의 - 

이론부터 실전까지 모든 것을 담은 자료구조/알고리즘