알고리즘의 시간 복잡도 중에서 자주 접할 수 있는 형태로는 다음과 같은 것들이 있다.
O(1)
상수 시간 알고리즘(Constant-time algorithm)의 수행시간은 입력의 크기에 영향을 받지 않는다.
상수 시간 알고리즘의 예로는 공식을 이용하여 답을 바로 계산해내는 알고리즘이 있다.
O(log n)
로그 시간 알고리즘(Logarithmic algorithm)은 대체로 단계마다 입력의 크기를 절반씩 줄여나간다.
n을 계속 2로 나눠가면서 1이 되도록 하는 데에 필요한 단계 수는 log2 n 이고, 따라서 이러한 알고리즘의 수행시간은 로그 시간이다.
로그의 밑수가 시간 복잡도에 나타나 있지 않음에 유의하라.
O(√n)
제곱근 시간 알고리즘(Square root algorithm)은 O(log n) 보다 느리지만, O(n)보다는 빠르다.
제곱근의 특별한 성질은 √n = n/√n이 성립한다는 것인데, 따라서 n개의 원소를 각각 O(√n)개씩의 원소로 이루어진 그룹O(√n)개로 나눌 수 있다.
O(n)
선형 시간 알고리즘(Linear algorithm)은 입력을 쭉 살펴보는 과정을 상수 번 수행한다.
대부분의 경우에 선형시간이 가장 효율적인 시간복잡도인데, 그 이유는 답을 구하기 위해서 입력을 적어도 한번은 쭉 살펴봐야 하기 때문이다.
O(n log n)
이 시간 복잡도는 입력을 정렬하는 과정의 시간 복잡도를 기술할 때 자주 사용한다. 그 이유는 효율적인 정렬 알고리즘의 시간 복잡도가 O(n log n)이기 때문이다. 또 다른 예로는 연산을 한번 수행할 때 마다 O(n log n)시간이 걸리는 자료구조를 사용하는 알고리즘이 있다.
O(n^2)
제곱 시간 알고리즘(Quadratic algorithm)은 보통 2중으로 중첩된 반복문을 사용한다.
O(n^2) 시간에 원소 두 개로 만들 수 있는 모든 조합을 한 번씩 살펴볼 수도 있다.
O(n^3)
세제곱 시간 알고리즘(Cubic algorithm)은 보통 3중으로 중첩된 반복문을 사용한다.
O(n^3) 시간에 원소 세 개로 만들 수 있는 모든 조합(triplet)을 한번씩 살펴볼 수도 있다.
O(2^n)
이 시간 복잡도는 입력 원소로 만들 수 있는 모든 부분집합을 한 번씩 살펴보는 알고리즘의 시간 복잡도를 기술할때 자주 사용한다.
예를 들어, {1,2,3}으로 만들 수 있는 부분집합을 모두 나열하면 0, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} 과 같다.
O(n!)
이 시간 복잡도는 입력 원소로 만들 수 있는 모든 순열을 한 번씩 살펴보는 알고리즘의 시간 복잡도를 기술할때 자주 사용한다.
예를 들어 {1,2,3}으로 만들 수 있는 순열을 모두 나열하면, (1,2,3), (1,3,2), (2,3,1), (3,1,2), (3,2,1)과 같다.
알고리즘의 시간 복잡도가 어떤 상수 K에 대해 O(n^k)를 넘지 않으면 다항 시간 알고리즘(Polynomial algorithm)이라고 한다. 앞에서 살펴본 시간 복잡도 중에서 O(2^n)과 O(n!)을 뺀 나머지는 모두 다항 시간이다.
실제 상황에서는 대개의 경우에 상수 k가 작으며, 따라서 시간 복잡도가 다항 시간이라는 것은 알고리즘이 매우 큰 입력까지도 처리할 수 있다는 것과 비슷한 의미이다.
중요한 개념 중 하나인 NP-하드 문제(NP-hard problem)는 아직 다항 시간 알고리즘이 알려지지 않은 것들의 집합이다.
출처: https://itlearning.tistory.com/entry/자주-접할-수-있는-시간-복잡도 [Write Code:티스토리]