[algorithm 이론] 자주 접할 수 있는 알고리즘시간 복잡도 정리

알고리즘의 시간 복잡도 중에서 자주 접할 수 있는 형태를 정리한 것이다.

 

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(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,1,3), (2,3,1), (3,1,2), (3,2,1)과 같다.

 

 

 

 

 

 

 

 

베타존 : 네이버쇼핑 스마트스토어