알고리즘의 정의
컴퓨터가 계산이나 기타 문제 해결 작업을 수행할 때 따라야 하는 프로세스 또는 일련의 규칙
문제 풀이에 필요한 계산 절차 또는 처리 과정의 순서를 뜻함
알고리즘 문제는 답을 찾는 것도 중요하지만 효율적인 방식으로 푸는 것도 중요하다.
문제의 효율을 따질때는 보통 시간복잡도와 공간복잡도를 고려한다.
공간복잡도
공간 복잡도란 프로그램 실행과 완료에 얼마나 많은 공간(메모리)가 필요한지를 나타낸다.
알고리즘을 실행시키기 위해 필요한 공간(space)는 두 가지로 나눌 수 있다.
- 알고리즘과 무관한 공간, 즉 고정 공간
- 코드가 저장되는 공간, 알고리즘 실행을 위해 시스템이 필요로 하는 공간 등
- 알고리즘과 밀접한 공간, 즉 가변 공간
- 문제를 해결하기 위해 알고리즘이 필요로 하는 공간.
- 변수를 저장하는 공간, 순환 프로그램일 경우 순환 스택(recursion stack) 등
시간복잡도
시간복잡도란 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는지를 나타낸다.
그리고 시간복잡도는 여러가지 표기법이 있지만 주로 Big-O 표기법을 통해 표현한다.
- Big-O(빅-오) ⇒ 상한 점근
- Big-Ω(빅-오메가) ⇒ 하한 점근
- Big-θ(빅-세타) ⇒ 그 둘의 평균
- 위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다.
한마디로 Big-O 표기법은 최악의 상황을 가정하여 "최대 이정도 시간까지 걸릴 수 있다"고 하는 것이다.
기본적으로 최악의 상황을 바라지않고 시간복잡도를 계산하는 것보다
최악의 상황을 대비하여 알고리즘을 구현하는 것이 바람직한 것 같다.
Big-O 표기법의 종류
O(1)
- O(1)는 일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.
O(n)
- O(n)은 선형 복잡도(linear complexity)라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.
O(log n)
- O(log n)은 로그 복잡도(logarithmic complexity)라고 부르며, Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
O(n^2)
- O(n^2)은 2차 복잡도(quadratic complexity)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.
O(2n)
- O(2n)은 기하급수적 복잡도(exponential complexity)라고 부르며, Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.
오른쪽으로 갈수록 성능이 나빠진다 다시말해 시간복잡도가 좋지않다.
시간복잡도를 시각화한 그래프와 자료구조, 정렬알고리즘에 따른 시간복잡도가 정리된 표도 있으니 참고하면 좋을 것 같다.
시간 복잡도 vs 공간 복잡도
시간 복잡도는 얼마나 빠르게 실행되는지, 공간 복잡도는 얼마나 많은 자원(메모리 공간)이 필요한지를 판단한다.
시간 복잡도와 공간 복잡도는 반비례하는 경향이 있어, 보통 알고리즘의 성능을 판단할 때는 시간 복잡도를 위주로 판단한다.
하지만 많은 데이터를 다루는 경우 공간 복잡도가 커지게 되고 프로그램이 메모리에 올라가지 않아 실행할 수 없게 될 수도 있다.
따라서 알고리즘 작성 시 공간 복잡도도 어느 정도 신경 써서 작성하는 것이 좋다.
참고자료
'알고리즘공부' 카테고리의 다른 글
| [자료구조] 스택(Stack) (0) | 2024.11.28 |
|---|---|
| [자료구조] 큐(Queue) (0) | 2024.11.28 |