1. 정의

점근적 실행시간이란, 입력값 N이 커질 때, 그러니까 입력값이 무한대를 향할 때 함수의 실행시간 추이를 말한다. 점근적 실행시간을 시간복잡도라고도 하는데, 이 시간복잡도를 표기하는 방법중 하나가 상한을 의미하는 big - O다.

2. 실행시간과 메모리 용량

대부분의 경우 실행시간과 메모리 용량은 반비례하지만 그렇지 않은 알고리즘의 경우가 드물지만 몇 있다. 이는 알고리즘의 주요한 특징 중 하나다.

3. 종류

O(1), 상수형태 : 입력값이 아무리 커도 실행시간이 일정하다. 가장 이상적인 알고리즘이며 이런 알고리즘은 만들기 어려운 정도가 아니라 거의 불가능에 가깝다. 해시 테이블의 조회나 삽입같은 경우가 해당한다.

O(log n), 로그형태 : 실행시간이 입력값에 영향을 받지만, 그래도 웬만한 입력값에는 크게 영향을 받지 않는다. 이진 검색이 여기 해당한다.

O(n), 선형형태 : 입력값만큼 실행시간에 크게 영향을 받는다. 알고리즘을 수행하는데 걸리는 시간은 입력값에 비례한다. 이런 시간복잡도를 갖는 알고리즘을 선형시간 알고리즘이라고 한다. 보통 모든 입력값을 한번 이상 살펴보는 과정이 있다. 예를 들어서 친구 집인 103동에 도착했는데 알고 있는 정보가 고작 103동뿐이라면 최악의 경우 모든 호를 다 뒤져야 할 것이다. 이런 경우가 여기 해당된다.

O(n log n), 선형 로그형태 : 효율 좋은 알고리즘들이 여기 해당된다. 모든 수를 한번 이상 비교해야하는 비교기반 정렬 알고리즘은 아무리 좋은 알고리즘이라도 이것보다 빠를 수 없다. 퀵정렬, 병합정렬, 힙정렬들이 이런 시간복잡도를 가진다.

O(n^2), O(n^3), 다차형태 : 버블정렬같은 비효율적인 정렬 알고리즘이 여기 속한다. 선형형태 시간복잡도의 경우는 친구가 어디 사는지 동은 알았는데, 만약 몇동인지도 모른다 하면 그 단지를 다 뒤져야 할 것이다. 이런 경우가 (동수) X (호수)이며, O(n^2)에 속한다. 심지어 친구가 몇단지인지도 모른다면 그 아파트, 그 마을 전체를 다 뒤져야 할 것이다. 이런 경우가 (단지 수) X (동수) X (호수)가 되어 O(n^3)에 속한다.

O(2^n), 지수형태 : 피보나치 수를 재귀를 이용하여 구하는 경우가 여기 해당된다. 다차형태와 모양은 비슷해보이지만 지수형태가 훨씬 더 크다. n이 15만 돼도 145배 이상 차이가 나기 시작한다.

O(n!), 팩토리얼 형태 : 각 도시를 방문하고 돌아오는 외판원 문제를 모든 경우를 검사하는 브루트포스로 풀 때 등이 해당된다. n이 늘어남에 따라 급격하게 증가한다. n이 16이라고 쳤을 때, 상수형태는 1, 선형 형태는 16이고 지수형태도 65536에 해당하는 반면에 팩토리얼 형태는 무려 20922789888000이다.

4. 시간복잡도의 최악의 경우

퀵정렬 문제에서, 입력이 [1, 2, 3, 4, 5, 6, 7]으로 주어졌을 때랑 [1, 4, 3, 7, 8, 6, 5]로 주어졌을 때랑 다를 것이다. 일반적인 상식과 다르지만 [1, 2, 3, 4, 5, 6, 7]로 주어진 경우는 최악의 경우이다. 이런 경우 48번의 연산을 수행 할 것이다. 하지만 위에 같이 적은 최선의 경우는 고작 18번만 연산을 하면 된다.

5. 시간복잡도의 상한의 경우

시간복잡도는 ‘최악’을 의미하지 않는다. ‘상한’을 의미한다.

꼬불꼬불한 복잡한 함수 f(n)이 있을 경우 이 함수의 실행 상한을 빅오라고 하는것이고, 실행 하한을 빅오메가라고 하는 것이다. 평균은 빅세타라고 칭한다. 입력의 경우가 어떻든, 가장 빨리 실행될 때와 가장 느리게 실행될 때를 칭하는 것이다.