[알고리즘] 시간복잡도 순서(Big O)

빅오(Big O)표기법으로 보는 시간 복잡도

프로그래밍에서 알고리즘의 시간 복잡도(Time Complexity)는 알고리즘이 어떤 문제를 해결하는 데 필요한 시간이 입력의 크기에 따라 어떻게 변하는지를 나타내는 척도입니다. 

 

시간 복잡도를 표기하는 데는 여러 가지 방법이 있지만, 가장 널리 사용되는 표기법은 빅 오(Big O) 표기법입니다. 

 

빅 오 표기법으로 표현된 시간 복잡도의 종류를 빠른 순서부터 느린 순서대로 나열하면 다음과 같습니다.

출처 : https://medium.com/@burakkocakeu/what-are-these-notations-o-n-o-nlogn-o-n%C2%B2-with-time-complexity-of-an-algorithm-7c40537e569c

O(1) 상수 시간(Constant Time)

입력 데이터의 크기와 상관없이 알고리즘의 실행 시간이 일정합니다.

O(log n) 로그 시간(Logarithmic Time)

입력 데이터의 크기가 커질수록, 실행 시간이 로그 적으로 증가합니다.

이진 탐색(Binary Search)이 여기에 해당합니다.

O(n) - 선형 시간(Linear Time)

알고리즘의 실행 시간이 입력 데이터의 크기에 비례하여 증가합니다.

배열을 순회하는 경우가 이에 해당합니다.

O(n log n) - 선형 로그 시간(Linearithmic Time)

대표적으로 병합 정렬(Merge Sort)이나 퀵 정렬(Quick Sort) 같은 고급 정렬 알고리즘이 이에 해당합니다.

O(n^2) - 제곱 시간(Quadratic Time)

입력 데이터의 크기의 제곱에 비례하여 실행 시간이 증가합니다.

간단한 정렬 알고리즘인 버블 정렬(Bubble Sort)이나 삽입 정렬(Insertion Sort)이 여기에 해당합니다.

O(n^3) - 세제곱 시간(Cubic Time)

입력 데이터의 크기의 세제곱에 비례하여 실행 시간이 증가합니다.

일부 행렬 곱셈 알고리즘이나 그래프 알고리즘에서 볼 수 있습니다.

O(2^n) - 지수 시간(Exponential Time)

입력 데이터의 크기가 커질수록, 실행 시간이 지수적으로 증가합니다.

여러 분할 정복 알고리즘들이 이에 해당할 수 있습니다.

O(n!) - 팩토리얼 시간(Factorial Time)

입력 데이터의 크기에 대한 팩토리얼에 비례하여 실행 시간이 증가합니다.

가장 대표적인 예는 여행하는 세일즈맨 문제(TSP, Traveling Salesman Problem)를 브루트 포스로 해결할 때입니다.

 

팩토리얼?

n개의 요소를 가진 데이터 세트를 완전 탐색(Brute Force) 방식으로 처리하는 경우, 가능한 모든 조합을 확인해야 하므로, 실행 시간이 n의 팩토리얼에 비례하여 증가합니다. 

n!은 1부터 n까지 모든 정수의 곱을 의미하므로, 입력 데이터의 크기가 조금만 커져도 실행 시간이 매우 길어질 수 있습니다.
예를 들어, n = 3인 경우, 3! = 3 x 2 x 1 = 6이므로, 6가지 경우의 수를 모두 확인해야 합니다. 

하지만 n이 10이라면, 10! = 3,628,800가지 경우의 수를 모두 확인해야 하며, n의 값이 더 커지면 실행 시간은 기하급수적으로 늘어나게 됩니다.