복잡도

이것이 취업을 위한 코딩 테스트다 with 파이썬을 공부하면서 정리한 내용입니다.

---

개요

• 복잡도는 알고리즘의 성능을 나타내는 척도
• 복잡도는 시간 복잡도와 공간 복잡도로 구분
  • 시간 복잡도: 특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는지를 의미
  • 공간 복잡도: 특정한 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미
• 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘
• 복잡도를 측정함으로써 계산할 수 있는 것
  • 시간 복잡도: 알고리즘을 위해 필요한 연산의 횟수
  • 공간 복잡도: 알고리즘을 위해 필요한 메모리의 양
• 보통 시간 복잡도와 공간 복잡도는 일종의 Trade-off가 성립
• 메모리를 조금 더 많이 사용하는 대신에 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있음
• 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가 있는데, 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법으로 메모제이션 기법이 있음

---

시간 복잡도

• 알고리즘 문제를 풀 때 보통 복잡도는 시간 복잡도를 의미
• 코딩 테스트에서 시간 제한은 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸리는 시간을 의미
• 시간 복잡도를 표현할 때는 빅오 표기법을 사용
  • 빅오 표기법: 가장 빠르게 증가하는 항만을 고려하는 표기법, 즉 함수의 상한만을 나타냄
• 예를 들어, N개의 데이터를 받아 차례로 더해주는 프로그램이 있다고 할 때 연산 횟수는 N에 비례
• 이 프로그램에서 합계 변수를 0으로 초기화하거나 합계 변수를 출력하는 부분도 있으나 이런 연산 횟수는 상대적으로 N이 커짐에 따라 무시할 수 있을 정도로 작아짐
• 따라서 소스코드에서 가장 영향력이 큰 부분은 N에 비례하는 연산을 수행하는 반복문 부분이므로 시간 복잡도를 $O(N)$로 표기

array = [3, 5, 1, 2, 4]  # 5개의 데이터(N = 5)
summary = 0              # 합계를 저장할 변수

# 모든 데이터를 하나씩 확인하며 합계를 계산
for x in array:
    summary += x

# 결과를 출력
print(summary)

15

• 다음 소스코드에서는 a와 b에 값을 대입하는 대입 연산과 출력 함수를 무시하고 보면, 단순히 더하기 연산 한 번이 수행되기 때문에 시간 복잡도는 $O(1)$

a = 5
b = 7

print(a + b)

12

• 다음 소스코드에서는 array 리스트 변수의 길이가 N개일 때, $O(N^2)$의 시간 복잡도를 가짐
• 2중 반복문을 이용하여 각 원소에 대하여 다른 모든 원소에 대한 곱셈 결과를 매번 출력하기 때문에 $N \times N$이 되어 시간 복잡도가 $O(N^2)$

array = [3, 4, 1, 2, 4] # 5개의 데이터(N = 5)

for i in array:
    for j in array:
        temp = i * j
        print(temp)

• 다만 소스코드에서 내부적으로 다른 함수를 호출한다면 내부 함수의 시간 복잡도까지 고려해야 하기 때문에 항상 2중 반복문의 시간 복잡도가 $O(N^2)$은 아님
• 그렇기 때문에 소스코드를 정확히 분석한 뒤에 시간 복잡도를 계산해야 함
• 퀵 정렬의 경우 평균 시간 복잡도가 $O(NlogN)$이지만 최악의 경우 시간 복잡도는 $O(N^2)$
• 일반적으로 코딩 테스트에서 최악의 경우에 대한 연산 횟수가 중요

빅오 표기법

• 시간 복잡도 표에서 위쪽에 있을수록 더 빠름

빅오 표기법	명칭
$O(1)$	상수 시간
$O(logN)$	로그 시간
$O(N)$	선형 시간
$O(NlogN)$	로그 선형 시간
$O(N^2)$	이차 시간
$O(N^3)$	삼차 시간
$O(2^n)$	지수 시간

• 특정 알고리즘의 시간 복잡도가 $O(N^k)$일 때 이를 다항 시간에 동작하는 알고리즘이라고 말하며 이차 시간, 삼차 시간 등이 모두 다항 시간에 해당
• 이론적으로 특정한 문제가 다항 시간 알고리즘으로 풀 수 잇을 때 해당 알고리즘은 풀 만한 알고리즘으로 분류되지만, 실제로는 그렇지 않음
• 일반적으로 코딩 테스트 환경에서 $O(N^3)$을 넘어가면 문제 풀이에서 사용하기 어려움
• 각기 다른 시간 복잡도의 연산 횟수가 N의 크기에 따라 달라지는 정도는 다음과 같음

	N이 1,000일 때의 연산 횟수
$O(N)$	1,000
$O(NlogN)$	9,966
$O(N^2)$	1,000,000
$O(N^3)$	1,000,000,000

• 빅오 표기법이 항상 절대적인 것은 아님
• 연산 횟수가 $3N^3 + 5N^2 + 1000000$인 알고리즘에서 빅오 표기법에서는 차수가 가장 큰 항만 남기기 때문에 $O(N^3)$으로 표기되지만, 실제로 N이 작을 때는 상수 값인 1000000이 미치는 영향력이 큼
• 빅오 표기법으로 표시한 시간 복잡도가 동일하더라도 알고리즘의 내부 로직 및 차수가 낮은 항의 영향에 따라 실제 수행되는 연산 횟수는 다를 수 있음

시간 복잡도에서의 연산은 프로그래밍 언어에서 지원하는 사칙 연산, 비교 연산 등과 같은 기본 연산을 의미

• 시간 복잡도 분석은 문제 풀이의 핵심
• 문제의 조건부터 확인하면 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지 눈치 챌 수 있음
• 시간 제한이 1초인 문제에 대한 예
  • N의 범위가 500인 경우: 시간 복잡도가 $O(N^3)$인 알고리즘을 설계하면 문제를 풀 수 있음
  • N의 범위가 2,000인 경우: 시간 복잡도가 $O(N^2)$인 알고리즘을 설계하면 문제를 풀 수 있음
  • N의 범위가 100,000인 경우: 시간 복잡도가 $O(NlogN)$인 알고리즘을 설계하면 문제를 풀 수 있음
  • N의 범위가 10,000,000인 경우: 시간 복잡도가 $O(N)$인 알고리즘을 설계하면 문제를 풀 수 있음

---

공간 복잡도

• 공간 복잡도를 표기할 때도 빅오 표기법을 이용
• 메모리 사용량에도 제한이 있으며, 일반적으로 메모리 사용량 기준은 MB 단위로 제시
• 코딩 테스트에서는 보통 메모리 사용량을 128~512MB로 제한
• 일반적인 경우 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘을 설계해야 함

---

시간과 메모리 측정

• 알고리즘의 소요 시간을 확인해야 제대로 알고리즘을 작성하고 있는지 확인할 수 있음
• 프로그램 수행 시간을 측정하는 것은 알고리즘의 효율성을 측정하는 가장 기본적인 방법
• 특정 프로그램의 수행 시간을 측정하는 소스코드 예시는 다음과 같음

import time

start_time = time.time() # 측정 시작

# 프로그램 소스코드
...

end_time = time.time() # 측정 종료
print('time:', end_time - start_time) # 수행 시간 출력

• 선택 정렬을 사용할 때 최악의 경우 시간 복잡도가 $O(N^2)$이며, 파이썬의 기본 정렬 라이브러리는 최악의 경우 시간 복잡도 $O(NlogN)$을 보장하여 상대적으로 빠름
• 선택 정렬과 파이썬의 기본 정렬 라이브러리의 속도를 비교할 때는 다음과 같이 소스코드를 작성

from random import randint
import time

# 배열에 1부터 100 사이의 정수를 10,000개 삽입
original_array = [randint(1, 100) for _ in range(10000)]
array1 = original_array.copy()
array2 = original_array.copy()

# 선택 정렬 성능 측정
start_time = time.time()

# 선택 정렬 소스코드
for i in range(len(array1)):
    min_index = i # 가장 작은 원소의 인덱스
    for j in range(i + 1, len(array1)):
        if array1[min_index] > array1[j]:
            min_index = j
    array1[i], array1[min_index] = array1[min_index], array1[i] # 스와프

end_time = time.time() # 측정 종료
print('선택 정렬 성능 측정:', end_time - start_time) # 수행 시간 출력

# 기본 정렬 라이브러리 성능 측정
start_time = time.time()

# 기본 정렬 라이브러리 사용
array2.sort()

end_time = time.time() # 측정 종료
print('기본 정렬 라이브러리 성능 측정:', end_time - start_time) # 수행 시간 출력

선택 정렬 성능 측정: 20.182358741760254
기본 정렬 라이브러리 성능 측정: 0.0012326240539550781

• 코딩 테스트 문제를 풀 때는 가독성을 해치지 않는 선에서 최대한 복잡도가 낮게 프로그램을 작성해야 함