O(n!) - 팩토리얼 시간
주어진 배열의 원소들을 가능한 모든 순서로 배열하는 것을 순열 생성의 모든 경우의 수이다. 여기서 순열은 일반적인 순열인 직순열로 일직선상의 배열이다.
이러한 연산에서 n개 원소는 n! 개의 순열이 존재하고, 각 순열을 생성하는 데 걸리는 시간을 포함한 전체 시간 복잡도는 n! * n = O(n!)이다.
순열 생성
배열 [1, 2, 3]가 있을 때, 가능한 모든 순열은 다음과 같다.
[1, 2, 3], [1, 3, 2],
[2, 1, 3], [2, 3, 1],
[3, 1, 2], [3, 2, 1]
총 3! = 6가지 경우가 존재한다.
코드로 표현하면 다음과 같다.
def permutations(arr):
if len(arr) <= 1:
return [arr]
result = []
for i in range(len(arr)):
# ':' 슬라이싱, :끝 : 처음부터 끝 인덱스 바로 전까지(끝 비포함), 시작: : 시작 인덱스부터 끝까지
# => :i i인덱스를 제외한 그 앞의 집합, i+1: 다음 인덱스까지의 집합, 길이 초과하는 경우 빈 배열
rest = arr[:i] + arr[i+1:]
for p in permutations(rest): #
result.append([arr[i]] + p) # append : 리스트 객체 맨 끝에 새로운 요소 추가
return result
print(permutations([1, 2, 3]))
"""
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
"""
1. 하나의 인덱스를 고정한다.
2. 나머지 요소들의 순열을 재귀적으로 구한다.
3. 그 앞에 고정 요소를 붙여서 순열을 구성한다.
이 방식은 재귀 호출마다 n-1개의 원소로 순열을 생성하며, 전체 시간 복잡도는 O(n!)이다.
외판원 문제(TSP, Travelling Salesman Problem)
외판원이 n개의 도시를 모두 방문하고 출발점으로 돌아오는 최단 경로를 찾는 문제이다.
NP-hard 문제의 대표적인 예시로 자주 사용된다.
조건
- 각 도시는 정확히 한 번씩만 방문한다.
- 모든 도시 간의 거리가 주어진다.
이 문제는 다양한 해결법이 존재하지만 그중에서 브루트포스 접근법이 O(n!)의 시간 복잡도를 가진다.
브루트포스
4개 도시 A, B, C, D가 있을 때, 가능한 모든 경로를 확인한다.
A -> B -> C -> D -> A
A -> B -> D -> C -> A
...
다시 출발점으로 돌아오기 때문에 원순열로 취급할 수 있어 시작점을 A로 고정하고 모든 경로를 구한다.
나머지 n-1개 도시의 순열을 구한다. (n-1)!
4개 도시 -> (4 - 1)! = 6가지
import itertools
def tsp_bruteforce(distance):
# distance : 2D 배열, distance[i][j] : 도시 i에서 j로의 거리
n = len(distance)
cities = list(range(1, n)) # 시작 도시(0번)를 고정한 상태에서 나머지 도시의 순열을 생성
min_cost = float('inf')
best_path = None
# itertools.permutations : 순열을 생성해준다.
# 내부적으로 최적화가 잘되어있어 메모리 효율이 좋다. 시간복잡도는 그대로 O(n!)
for path in itertools.permutations(cities):
current_cost = 0
current_city =0
for next_city in path:
current_cost += distance[current_city][next_city]
current_city = next_city
current_cost += distance[current_city][0]
if current_cost < min_cost:
min_cost = current_cost
best_path = [0] + list(path) + [0]
return min_cost, best_path
distance = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
city_names = ["A", "B", "C", "D"]
cost, path = tsp_bruteforce(distance)
print(f"Min cost : {cost}")
print(f"Best path : {path}")
named_path = ' -> '.join(city_names[i] for i in path)
print(f"Best path : {named_path}")
"""
Min cost : 80
Best path : [0, 1, 3, 2, 0]
Best path : A -> B -> D -> C -> A
"""
순열생성
O((n-1)!), n-1개 도시의 모든 순열 생성
각 경로 비용 계산
O(n), 각 순열마다 n개 도시를 거쳐가는 비용 계산
전체 시간복잡도
O(n * (n-1)!) = O(n!)
브루트포스의 가장 큰 문제점은 도시의 수가 조금만 늘어나도 실행 시간이 급격하게 증가하여 계산이 불가능해진다.
계산 시간 테스트 코드
도시의 개수를 추가하고 경과시간을 체크해 본다.
import time
import itertools
import random
def generate_distance_matrix(n):
matrix = [[0]*n for _ in range(n)]
for i in range(n):
for j in range(i+1, n):
dist = random.randint(1, 99)
matrix[i][j] = dist
matrix[j][i] = dist
return matrix
def tsp_bruteforce(distance):
n = len(distance)
cities = list(range(1, n))
min_cost = float('inf')
best_path = None
for path in itertools.permutations(cities):
current_cost = 0
current_city = 0
for next_city in path:
current_cost += distance[current_city][next_city]
current_city = next_city
current_cost += distance[current_city][0]
if current_cost < min_cost:
min_cost = current_cost
best_path = [0] + list(path) + [0]
return min_cost, best_path
# 테스트 도시 수: 4 ~ 10
for n in range(4, 11):
print(f"\n=== TSP for {n} cities ===")
distance = generate_distance_matrix(n)
start = time.perf_counter()
cost, path = tsp_bruteforce(distance)
end = time.perf_counter()
elapsed = end - start
print(f"Min cost: {cost}")
print(f"Best path (index): {path}")
print(f"Elapsed time: {elapsed:.6f} seconds")
"""
=== TSP for 4 cities ===
Min cost: 209
Best path (index): [0, 1, 2, 3, 0]
Elapsed time: 0.000019 seconds
=== TSP for 5 cities ===
Min cost: 167
Best path (index): [0, 2, 1, 3, 4, 0]
Elapsed time: 0.000019 seconds
=== TSP for 6 cities ===
Min cost: 159
Best path (index): [0, 3, 1, 2, 5, 4, 0]
Elapsed time: 0.000077 seconds
=== TSP for 7 cities ===
Min cost: 186
Best path (index): [0, 5, 2, 1, 4, 3, 6, 0]
Elapsed time: 0.000502 seconds
=== TSP for 8 cities ===
Min cost: 161
Best path (index): [0, 3, 1, 2, 4, 6, 7, 5, 0]
Elapsed time: 0.019747 seconds
=== TSP for 9 cities ===
Min cost: 172
Best path (index): [0, 4, 5, 8, 2, 7, 3, 1, 6, 0]
Elapsed time: 0.157354 seconds
=== TSP for 10 cities ===
Min cost: 236
Best path (index): [0, 2, 3, 6, 1, 9, 4, 5, 8, 7, 0]
Elapsed time: 1.502671 seconds
"""
10개까지의 테스트는 실행이 되었지만 테스트를 위해 사용한 웹 컴파일러는 15초 이상의 작업은 실패로 처리하는데 11개의 도시 테스트에서 실패로 처리되었다.
수치를 추정해 보면,
10개의 도시인 경우 10! = 3,628,800개의 경우의 수를 처리하는데 1.5초의 소요 시간이 걸렸다.
11개의 도시는 11! = 39,916,800개로 약 11배가 증가했으므로 추정 소요 시간은 16.5초로 예상된다.
| 도시 수 |
순열 수 |
예상 시간 (초) |
| 10 |
3,628,800 |
1.5 |
| 11 |
39,916,800 |
16.5 |
| 12 |
479,001,600 |
198+ 초 (약 3.3분) |
| 13 |
6,227,020,800 |
약 27~30분 |
| 14 |
87,178,291,200 |
5시간 이상 |
사용법은 간단하지만 한계가 명확하기 때문에 실용적이지 않아 다른 효율적인 방법으로 대체된다.
동적 계획법 (O(n^2 * 2^n))
정확한 해를 구할 수 있는 방법으로, 방문 상태를 비트마스크로 표현하여 중복 계산을 줄인다.
근사 알고리즘(다항시간)
최적 해는 아니지만, 일정한 오차 범위 내에서 빠르게 좋은 해를 보장한다.
대표적으로 MST 기반 알고리즘이 있다.
휴리스틱 기법
엄밀한 최적 보장은 없지만, 실제 환경에서 유용하게 사용된다.
유전 알고리즘(GA)이나 시뮬레이티드 어닐링(SA)들이 이에 해당한다.
