선형 시간(linear time) 알고리즘

입력 크기 대비 걸리는 시간 그래프가 직선이 되는 알고리즘.
선형 시간 알고리즘은 대개 가장 좋은 알고리즘인 경우가 많다. 주어진 입력을 최소한 한 번씩만 봐도 선형 시간이 걸리기 때문이다.

log2N

입력 N에 대해 계속 절반(=밑이 2)으로 나누어 1 이하가 될 때까지 몇 번인지를 나타낸다.
입력 크기 대비 걸리는 시간이 느리게 증가하므로 선형 이하 시간(sublinear time) 알고리즘이라고 한다.

지수 시간(exponential time)

2N과 같이 N이 하나 증가할 때마다 걸리는 시간이 배로 증가하는 것을 뜻함.
가장 큰 수행 시간 중 하나다.

효율의 경계

다항 시간 vs 지수 시간 = 효율적 vs 효율적이지 못함

시간 복잡도가 높다

입력의 크기가 증가할 때 수행 시간이 더 빠르게 증가한다는 의미
입력 크기가 충분히 작을 때, 시간 복잡도가 높은 알고리즘이 더 빠르게 동작할 수도 있다.

O(N2)

오더(Order) 엔 제곱