[Algorithm] 어떤 알고리즘이 더 빠르고 효율적인가? - 시간복잡도 (5)

[※ 주의 ※] 아래를 이해하지 않고 이 글을 볼 경우, 이해가 되지 않는 부분이 있을 수 있습니다.

 

1. [Algorithm] 어떤 알고리즘이 더 빠르고 효율적인가? - 시간복잡도 (4)

---

 

자, 대략적인 시간 복잡도 간 속도를 알았으니, 구체적으로 시간 복잡도를 어떻게 활용할 수 있는지 생각하여보자.

 

시간 복잡도는 말 그대로 "대략적인 시간"에 관한 이야기이다. 다른 말로, 대충 최대 어느 정도의 시간 및 연산 횟수가 소요될 지 어림잡을 수 있다는 이야기이다. 실제 코딩 테스트나 각종 대회에서도 필요한것은 소요되는 시간이지 시간 복잡도 그 자체가 아니다.

 

코딩계에서 통용되는 하나의 관습이 있다.

 

1초당 연산 횟수는 대략 1억($10^9$)번이다.

구체적으로 말하자면 시간 제한이 1초라면 대략 1억번 연산 내로 문제를 풀어야 하고, 시간 제한이 2초라면 대략 2억번 연산 내로 문제를 풀어야 한다는 뜻이다.

 

그리고, 입력의 크기($N$)에 따라 문제의 제한시간 내에 들어올 수 있는 지 생각해보아야 한다.

 

만약 시간제한이 1초라고 가정하고, 각 입력의 크기에 따라 대략적인 시간 통과 여부를 알아보자.

 

1) $N = 1,000$

$N$이 1,000인 경우를 살펴보자.

 

- $O(N) \approx 1,000 < 10^9$

- $O(N\log N) \approx 1000*3 = 10^3 < 10^9$

- $O(N^2) \approx (10^3)^2 < 10^9$

- $O(N^3) \approx (10^3)^3 = O(10^9) \leq 10^9$

 

대략 시간 복잡도가 $O(N^2)$인 알고리즘까지는 안정적으로 시간 내에 수행할 수 있고, $O(N^3)$인 알고리즘은 아슬아슬하게 통과하거나 시간 초과가 날 가능성이 있다.

 

2) $N = 10,000$

$N$이 10,000인 경우를 살펴보자.

 

- $O(N) \approx 10,000 < 10^9$

- $O(N\log N) \approx 10000*4 = 40,000 < 10^9$

- $O(N^2) \approx (10^4)^2 = 10^8 \leq 10^9$

- $O(N^3) \approx (10^4)^3 = 10^{12} > 10^9$

 

대략 시간 복잡도가 $O(N\log N)$인 알고리즘까진 안정적으로 시간 내에 수행할 수 있다. 시간 복잡도가 $O(N^3)$인 알고리즘은 시간 초과가 가능성이 크고, $O(N^2)$인 알고리즘은 데이터에 따라 통과될 수도, 안 될수도 있는 알고리즘이다.

 

3) $N = 1,000,000$

$N$이 1,000,000인 경우를 살펴보자.

 

- $O(N) \approx 10^7 < 10^9$

- $O(N\log N) \approx 10^7 * 7 \leq 10^9$

- $O(N^2) \approx (10^7)^2 = 10^{14} > 10^9$

 

대략 시간복잡도가 $O(N)$인 알고리즘까진 안정적으로 시간 내에 수행할 수 있다. 시간 복잡도가 $O(N\log N)$인 알고리즘도 시간 내에 수행할 가능성은 높지만 장담할 수는 없고, $O(N^2)$이상의 시간 복잡도는 시간 내에 수행하기 불가능하다고 할 수 있다.

 

이 세 예시를 통해 실제 시간 복잡도를 대략적으로 수행하는 방법을 알아보았다.

 

다만, 시간 복잡도와 실제 수행시간, 연산 횟수와 관계가 있어도, 절대적으로 비례하지는 않는다. 다음과 같은 변수들이 있을 수 있기 때문이다. 따라서 실제 시행 시간은 실행해봐야 안다고 할 수 있겠다.

• 사용하는 언어 / 컴파일러의 종류 / 컴파일러의 코드 최적화 방법
• CPU의 캐시 메모리 사용
• 선형적이지 않은 알고리즘의 사용(ex. 재귀, 분할-정복...)
• 알고리즘 내부의 구현 방법

---

이제, 구체적인 코드를 통해 시간 복잡도를 계산하여 보자.

 

앞에서 시간 복잡도에 대한 설명을 할 때 무엇을 기준으로 시간 복잡도의 의미를 풀었는지 기억하나? "입력"을 $N$에 대입하였다. 즉, 입력이 얼마나 큰 지에 따라 시간 복잡도가 결정되었다.

 

그럼, 실제 코드에서 입력에 따라 실행되는 횟수의 차이를 보이는 문법은?

 

그렇다. 결국은 반복문(for, while) 과 같이 입력의 전체 데이터를 모두 살펴보는 문법이다. 그래서 시간 복잡도를 따질 때 반복문을 중심으로 따지는 것이다. (다만, 재귀함수의 호출 횟수, 트리의 깊이, 간선의 개수 등등 여러 방법으로 따질 수 있지만, 가장 지배적인 것을 생각하면 반복문이 되겠다.)

 

한 개의 for문을 통해 모든 데이터를 한 번 들여다 본다면 선형적으로 모든 데이터를 한 번씩 들여다 본 셈이니, $O(N)$이라 할 수 있다.

 

만약 두 개의 for문이 중첩되어 있다면, 데이터를 선형적으로 두 번씩 들여다 본 셈이니, $O(N^2)$이라 할 수 있다. (시간 복잡도(3)에서 설명하였듯, $O(N)*O(N) = O(N^2)$이다.)

 

예를 들어, 다음과 같은 Python으로 작성된 코드가 있다고 생각하여보자.

 

arr = [7, 5, 9, 1, 4, 2, 6]
 
for i in range(len(arr)):
    # min_idx : 가장 작은 원소
    min_idx = i
    # i보다 큰 인덱스의 원소들을 탐색
    for j in range(i+1, len(arr)):
        # 만약 arr[min_idx]보다 큰 값이 존재한다면...
        if arr[min_idx] > arr[j]:
            # 그 index를 min_idx로 업데아트
            min_idx = j
    # arr[i] 이후의 원소 중 가장 큰 원소와 arr[i] 간의 위치 교환
    arr[i], arr[min_idx] = arr[min_idx], arr[i]
 
print(arr)

 

위 코드에서 시간 복잡도를 계산할 때, 다음과 같이 두 곳에 방점을 찍어야 한다.

 

#arr = [7, 5, 9, 1, 4, 2, 6]
 
for i in range(len(arr)):
    # min_idx : 가장 작은 원소
    # min_idx = i
    # i보다 큰 인덱스의 원소들을 탐색
    for j in range(i+1, len(arr)):
        # 만약 arr[min_idx]보다 큰 값이 존재한다면...
        # if arr[min_idx] > arr[j]:
            # 그 index를 min_idx로 업데아트
            # min_idx = j
    # arr[i] 이후의 원소 중 가장 큰 원소와 arr[i] 간의 위치 교환
    # arr[i], arr[min_idx] = arr[min_idx], arr[i]
 
#print(arr)

 

반복문인 for문이 두 개 중첩되어 나타났으니, 이는 시간 복잡도가 $O(N^2)$이라 할 수 있다.

 

위의 코드의 정체인 선택 정렬(Selection Sort)의 시간 복잡도는 $O(N^2)$이다. 실제 연산 횟수를 계산해보면 $\frac{N(N+1)}{2} = O(N^2)$이므로, 꽤 정확하게 예측할 수 있다고 할 수 있다.

---

그러나, ★반복문만이 시간 복잡도를 결정하는 것은 아니다.★

 

이제, 다음 코드(함수)의 시간복잡도를 계산하여 살펴보자.

 

def dijkstra(start, end):
    # 우선순위 큐 이용
    queue = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정 (가장 먼저)
    heapq.heappush(queue, (0, start))
    distance[start] = 0
    # 부모 노드 초기화
    parent = [x for x in range(n+1)]
    while queue:
        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop()
        # 현재 노드가 처리된 노드라면 무시
        if distance[now] < dist:
            continue
        # 현재 노드와 인접한 노드들 확인
        for i in graph[now]:
            cost = dist + i[1]
            # 현재 노드를 거쳐 다른 노드로 이동하는 거리가 더 짧을 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(queue, (cost, i[0]))
                parent[i[0]] = now
                
    # 만약 경로를 직접 찾을 때는 재귀적으로 부모 노드 호출
    path = []
    now = end
    while now != start:
        path.append(now)
        now = parent[now]
    path.append(start)
    return path[::-1]

 

이번에도 위와 같은 방법 반복문을 중심으로 찾아보자.

 

def dijkstra(start, end):
    # 우선순위 큐 이용
    # queue = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정 (가장 먼저)
    # heapq.heappush(queue, (0, start))
    # distance[start] = 0
    # 부모 노드 초기화
    # parent = [x for x in range(n+1)]
    while queue:
        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        # dist, now = heapq.heappop()
        # 현재 노드가 처리된 노드라면 무시
        # if distance[now] < dist:
            # continue
        # 현재 노드와 인접한 노드들 확인
        for i in graph[now]:
            # cost = dist + i[1]
            # 현재 노드를 거쳐 다른 노드로 이동하는 거리가 더 짧을 경우
            # if cost < distance[i[0]]:
                # distance[i[0]] = cost
                # heapq.heappush(queue, (cost, i[0]))
                # parent[i[0]] = now
                
    # 만약 경로를 직접 찾을 때는 재귀적으로 부모 노드 호출
    # path = []
    # now = end
    while now != start:
        # path.append(now)
        # now = parent[now]
    # path.append(start)
    # return path[::-1]

 

음... 반복문만으로는 시간 복잡도를 계산할 수 있는 것처럼 보이지 않는다. 만약 while - for문이 중첩되어 시간 복잡도가 $O(N^2)$이라 생각하면 경기도 오산이다.

 

위의 코드의 정체인 다익스트라 알고리즘(Dijkstra Algorithm)의 실제 시간 복잡도는 $O(E\log V)$를 가진다. ($E$ : 간선의 개수, $V$ : 정점의 개수)

 

위의 코드의 시간 복잡도에서 왜 $\log$가 있냐고 묻는다면, 이는 우선순위 큐 자료구조를 활용해서 그렇다. 모르겠으면 넘어가도 좋다.

 

하여튼, 반복문만 세는 것이 시간 복잡도를 계산하는데 능사는 아니라는 것이 이 문단의 주요 내용이다.

 

결국 시간 복잡도의 추정은 연산 횟수를 중심으로 해야 한다는 것이고, 반복문을 중심으로 계산하되 데이터를 담는 자료 구조나 다른 특별한 연산 방법이 있는 지를 고려해야 한다.

---

지금까지 시간 복잡도에 관하여 처음부터 필요한 부분까지 알아보았다. 실제 코드를 작성할 때 시간 복잡도를 따지는 일은 굉장히 중요하다. 대략적인 경과 시간 및 필요 메모리 등등을 계산하고, 알고리즘을 더 효율적으로 개선하기 위한 하나의 초석이 되기 때문이다.

 

직접 여러 코드를 보면서 시간 복잡도를 계산하여보자. 그러면, 대략적으로 이 코드가 얼마나 효율적이고, 제한 시간 내에 계산할 수 있는 지를 어림 잡는 능력을 얻게 될 것이다.

 

도움이 되었다면 지나가는 길에 하트 하나 눌러주세요, 양질의 글을 쓰는데 하나의 동기부여가 됩니다😍

지적이나 오타 수정 댓글 환영합니다!!