Orchemi

Orchemi

I start where others stop.

[Algorithm] 복잡도

작성:    

업데이트:

카테고리:

태그: ,

복잡도

  • 알고리즘의 성능을 나타내는 척도
  • 시간복잡도와 공간 복잡도로 구분한다.


1. 시간 복잡도

  • 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미

  • 알고리즘을 위해 필요한 연산의 횟수

  • 알고리즘 문제를 풀 때 단순히 ‘복잡도’라고 하면 시간 복잡도 의미
  • 프로그램을 효율적으로 작성해야 프로그램이 시간 제한 내에 동작할 수 있다.


1.1. 표기법 ‘Big-O’

  • 가장 빠르게 증가하는 항만을 고려하는 표기법

  • 즉, 함수의 상한만을 나타낸다.

  • 시간 복잡도 분석은 문제 풀이의 핵심
  • 문제의 조건을 먼저 확인하여 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지 먼저 파악할 것


1.2. Big-O 활용예제 1

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

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

# 결과를 출력
print(summary)

실행결과는 다음과 같다.

15

위의 예제는 5개의 데이터를 받아 차례로 5회 더해준다.(N=5) 즉, 연산횟수는 N에 비례한다.

본 소스코드에서 가장 영향력이 큰 부분은 N에 비례하는 연산을 수행하는 반복문 부분이므로 시간 복잡도를 O(N)이라고 표기한다.


1.3. Big-O 활용예제 2

다음 예제는 어떤 시간 복잡도를 가질까.

a = 5
b = 7
print(a+b)

대입 연산과 출력 함수를 무시하면, 이 소스코드의 연산 횟수는 1이다. (더하기 연산 한 번) 이는 상수 연산으로, 시간 복잡도는 ‘O(1)’로 표현할 수 있다.


1.4. Big-O 활용예제 3

  • 다음 예제는 어떤 시간 복잡도를 가질까.
array = [3, 5, 1, 2, 4]  # 5개의 데이터(N=5)

for i in array:
    for j in array:
        temp = i * j
        print(temp)
  • 이 소스코드는 데이터의 개수(array 리스트 변수의 길이)가 N개일 때, O(N²)의 시간 복잡도를 가진다. 2중 반복문이기 때문이다.
  • 모든 2중 반복문의 시간 복잡도가 O(N²)인 것은 아니다. 내부 함수가 있는 경우 내부 함수의 시간 복잡도도 고려해주어야 한다.
  • 퀵 정렬(6장에서 학습)의 평균 시간 복잡도는 O(NlogN)이지만 최악의 경우 시간 복잡도는 O(N²)이다.
  • 최악의 경우의 시간 복잡도를 우선적으로 고려해야 한다.


1.5. 시간 복잡도 표

  • 위쪽에 있을수록 더 빠르다.
빅오 표기법 명칭
O(1) 상수 시간(Constant time)
O(logN) 로그 시간(Log time)
O(N) 상수 시간(Constant time)
O(N²) 이차 시간
O(N³) 삼차 시간
O(2ⁿ) 지수시간


1.6. 빅오 표기법의 한계

  • 빅오 표기법이 항상 절대적인 것은 아니다.
  • 실제 코딩테스트에서는 차수가 작은 항들을 완전히 무시하는 것도 곤란
3N³ + 5N² + 1,000,000인 알고리즘의 경우

빅오 표기법에서는 차수가 가장 큰 항만 남기 때문에 O(N³)으로 표기

하지만, 실제로 N이 작을 때는 상수 값인 1,000,000의 영향력이 크다.


1.7. 시간복잡도에 따른 알고리즘 선택

  • N의 범위가 500인 경우 : 시간복잡도가 O(N³)인 알고리즘을 설계하면 문제를 풀 수 있다.
  • N의 범위가 2,000인 경우 : 시간복잡도가 O(N²)인 알고리즘을 설계하면 문제를 풀 수 있다.
  • N의 범위가 100,000인 경우 : 시간복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.
  • N의 범위가 10,000,000인 경우 : 시간복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.


2. 공간복잡도

  • 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미

  • 알고리즘을 위해 필요한 메모리의 양

  • 시간 복잡도처럼 빅오 표기법을 이용
  • 코딩 테스트 문제는 대부분 리스트(배열)를 사용해서 풀어야 한다. 대부분의 문제는 다수의 데이터에 대한 효율적인 처리를 요구하기 때문

  • 정수형 자료인 int를 기준으로 리스트 크기에 따른 메모리 사용량을 확인해보자.

    • int a[1000]: 4KB
    • int a[1000000]: 4MB
    • int a[2000][2000]: 16MB
  • 코딩테스트에서는 보통 메모리 사용량을 128~512MB 정도로 제한한다. 즉, 일반적인 경우 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘 설계를 해야 한다는 의미


3. 시간과 메모리 측정

  • 다음의 코드를 통해 프로그램 수행 시간을 측정할 수 있다.
* 수행 시간 측정 소스코드

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

# 프로그램 소스코드
end_time = time().time()  # 측정 종료

# 수행 시간 출력
print("time :", end_time - start_time)

3.1. 예시

  • ‘선택 정렬’과 ‘파이썬 기본 정렬 라이브러리’의 속도 비교
  • ‘선택 정렬’ : 최악의 경우 O(N²)
  • ‘기본 정렬 라이브러리’ : 최악의 경우 O(NlogN)
from random import *
import time

# 배열에 10,000개의 정수를 삽입
array = []
for _ in range(10000):
    array.append(randint(1, 100))  # 1부터 100 사이의 랜덤한 정수

# 선택 정렬 프로그램 성능 측정
start_time = time.time()

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

end_time = time.time()  # 측정 종료

# 수행시간 출력
print("선택 정렬 성능 측정: ", end_time - start_time)


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

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

end_time = time.time()  # 측정 종료

# 수행시간 출력
print("기본 정렬 라이브러리 성능 측정: ", end_time - start_time)

출력값은 다음과 같다.

선택 정렬 성능 측정: 3.139763116836548
기본 정렬 라이브러리 성능 측정: 0.0

즉, 이렇게 알고리즘의 성능을 측정하기 위해서 시간 측정 라이브러리를 사용하는 습관을 기르는 것이 좋다.


4. 번외

  • 메모리를 더 소모하는 대신 얻을 수 있는 시간적 이점이 매우 큰 경우가 있다.
  • 메모이제이션(Memoization)
    • 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법
    • 8장에서 더 다룰 예정


REFERENCES

  • <이것이 취업을="" 위한="" 코딩테스트다="" with="" 파이썬="">, 나동빈, 한빛미디어

댓글남기기

참고