자료구조 01. 알고리즘 - 시간복잡도
알고리즘
알고리즘은 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합이다.
시간복잡도 : 알고리즘이 결과를 도출하는데 얼마나의 시간이 걸리는 지에 대한 값
공간복잡도 : 알고리즘이 결과를 도출하는데 얼마나의 공간이 필요한 지에 대한 값
좋은 알고리즘은 실행 시간이 빠르고 처리를 위해 필요한 기억 공간이 적은 알고리즘이다.
시간 복잡도
알고리즘을 직접 구현하지 않고 대략적인 효율성을 분석하는 것을 알고리즘 복잡도 분석이라 한다. 일반적으로 알고리즘의 복잡도를 이야기할 때 대개 시간 복잡도를 말한다.
시간복잡도는 빅오 표기법(Big-O), 빅오메가 표기법(Big omega), 빅세타 표기법(Big theta)으로 나타낼 수 있다.
빅오 표기법(Big-O)
- 시간의 상한 (최악의 경우)
- 해당 알고리즘은 빅오보다 더 오래 걸릴 수 없다.
빅오메가 표기법(Big omega)
- 시간의 하한 (최선의 경우)
- 해당 알고리즘은 빅오메가보다 더 빠를 수 없다.
- 실행 시간이 가장 적은 경우이므로 알고리즘 분석에서는 큰 의미가 없다.
빅세타 표기법(Big theta)
- 평균적인 경우
- 빅오와 빅오메가를 하나로 합쳐 표현한 것과 같다.
- 계산하기 어려운 경우가 많으며 최악의 상황에 대한 시간을 보장하지 못한다는 점에서 문제가 있다.
현실에서는 최악의 경우를 생각해야 하기 때문에 빅오 표기법을 많이 사용한다.
빅오 표기법(Big-O)
시간 복잡도 함수에서는 자료의 개수, 즉, n이 커질수록 차수가 가장 큰 항의 영향이 절대적이 된다.
빅오 표기법은 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용된다.
빅오 표기법을 얻는 간단한 방법은 기본 연산의 횟수가 다항식으로 표현되었을 때 다항식의 최고차항만을 남기고 다른 항들과 상수항을 버리는 것이다.
많이 사용되는 빅오 표기법을 복잡도 순으로 표시한 것이다.
O(1) :상수형
O(logn) :로그형
O(n) :선형
O(nlogn) :선형로그형
O(n^2) :2차형
O(n^3) :3차형
O(2^n) :지수형
O(n!) :팩토리얼형
실행 시간을 비교하면 다음과 같다.
O(1)< O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)
Leave a comment