2021. 10. 7. 20:29ㆍAlgorithm
알고리즘(Algorithm)이란?
* 어떤 문제의 해결을 위해 입력 된 자료를 토대로 하여 원하는 출력을 유도하여 내는 규칙의 집합
- 정렬의 종류
- 거품정렬(bubble sort)
- 선택정렬(selection sort)
- 삽입정렬(insertion sort)
- 퀵 정렬(quick sort)
- 진행 순서
- 입력
- 처리
- 출력
알고리즘의 성능 측정
- 시간 복잡도 (time complexity)
* 정확히는 시간을 계산한다기보단 연산 횟수를 계산하며, 입력값이 커짐에 따라 급격하게 횟수가 많아짐
* 알고리즘의 수행 시간을 측정하기 위한 개념으로 알고리즘을 수행에 필요한 연산이 몇 번 실행되는지를 숫자로 표기
* 이 연산의 개수는 상수가 아닌 입력한 데이터의 개수를 나타내는 n에 따라 변하게 됨
* 연산의 개수 n의 값에 따라 시간 복잡도를 나타낸 것을 시간 복잡도 함수라고 하며, 수식으로는 T(n)이라고 표기
* 양의 정수 n을 n번 더하는 알고리즘을 구현한다고 할 때, 이에 따른 시간 복잡도 함수 (아래)
- 공간 복잡도 (space complexity)
* 알고리즘을 수행하는 데 필요한 자원 공간의 양
* 공간 복잡도 함수는 [고정 공간 요구 + 가변공간 요구]로 나타낼 수 있으며, 수식은 아래와 같이 표기함
※ 고정 공간 : 입력과 출력의 횟수나 크기와 관계 없는 공간
※ 가변 공간 : 문제를 해결하기 위해 요구되는 추가 공간
* 팩토리얼의 구현을 한해 공간 복잡도 (아래)
* 재귀적으로 구현한 함수의 공간 복잡도 = O(n)이며, 위는 O(1)
※ 재귀(recursion) : 함수 내에서 자기 자신을 다시 호출하여 문제를 해결하는 방법
시간 복잡도 vs 공간 복잡도
* 효율적인 알고리즘은 실행 시간이 적게 걸리며, 자원을 적게 소모하는 것
* 하지만 시간과 공간은 반비례적인 경향이 있어 보통 알고리즘의 척도는 시간 복잡도를 위주로 판단함
* 즉, 시간 복잡도를 위해 공간 복잡도를 희생하는 경우가 많음
Big-O 표기법
* 다항식의 시간 복잡도 함수에서 입력값이 커져감에 따라 각 항의 결과값에 관여하는 정도가 달라지게 됨을 알 수 있기 때문에 시간 복잡도와 공간 복잡도를 표시할 때는 각 함수의 모든 항을 표시하지 않으며(가장 높은 차수의 항을 쓰며, 상수는 표기 생략), 상수 계수와 중요하지 않은 항목을 제거한 점근적 표기법을 사용
* 점근적 표기법(asymptotic notation)에는 Big-θ, Big-O, Big-Ω 등이 있지만 가장 많이 사용되는 것은 점근적 상한선을 제공하는 Big-O 표기법
* 많이 쓰이는 Big-O 표기법은 아래와 같으며, 오른쪽으로 갈 수록 상한선이 높아짐
