시간 복잡도

시간 복잡도란 알고리즘을 수행할 때 걸리는 시간을 기준으로 효율성을 분석하는 것이다. 시간의 효율성이란 결국 알고리즘에서 비교와 교환 등이 일어날 때 연산자의 처리 횟수가 적다는 의미이며, 연산자의 처리횟수가 적다는 건 시간의 복잡도가 낮다는 의미이다. 따라서 시간 복잡도가 낮을 수록, 연산자의 사용 횟수가 적을수록 효율성이 높은 알고리즘이 된다.

Big-O 표기법

Big-O 표기법은 컴퓨터 과학에서 "대략"을 나타내는 공식적인 개념으로 최악의 경우에 대한 시간 복잡도를 나타내는 표현이다.

Big Ω 표기법

Big-O와 비슷한 Big Ω (omega) 표기법이 있는데 Big Ω는 최선의 경우를 나타낸다.

선형 탐색에서 최선의 경우는 배열의 처음에 찾고자 하는 값이 있는 상황이다. 이는 배열의 크기와 상관없이 Ω(1)이라고 나타낸다.
버블 정렬에서 최선의 경우를 생각해보면 버블 정렬은 교환이 이루어지지 않더라도 배열이 정렬된 사실을 모르기 때문에 여전히 n-1번의 배교를 해줘야 하낟. 그래서 최선의 경우는 Ω(n)로 표기한다.
선택 정렬 역시 배열이 정렬되었다는 것을 알 수 없어, 최소 값을 계속 찾아주어야 하므로 Ω(n^2)로 표기한다.
삽입 정렬은 정렬되지 않은 부분에서 정렬된 부분으로 옮겨갈 때, 정렬된 부분의 가장 큰 수와 배교하면 되기 때문에 Ω(n)로 표기한다.