youns119

게임 클라이언트 개발자를 꿈꾸는 중

[Algorithm] 알고리즘의 성능에 대해서

Date :   Updated :

📊 알고리즘의 성능

보통 우리가 알고리즘의 성능을 평가한다고 할 때, 기준이 되는 척도에는 5가지 젇도가 있다.

  1. 정확성
    • 해당 알고리즘이 입력값에 대해 필요한 절차를 거쳐 출력값을 도출하기까지의 과정이 정확한지.
  2. 명확성
    • 알고리즘의 흐름이 얼마나 명확하고 단순한지.
  3. 최적성
    • 더 이상의 개선이 필요 없을 정도로 최적화가 잘 되어 있는지.
  4. 수행량
    • 요구되는 기능이 작동하기 위해 필요한 작업 수행의 양.
  5. 메모리 사용량
    • 작업을 수행하기 위해 필요한 메모리의 양.

이 중에서도 '알고리즘'의 성능을 평가할 때 가장 보편적으로 사용되는 것이 '수행량'과 '메모리 사용량'이다. 그리고 이 두 가지를 우리는 시간 복잡도와 공간 복잡도라고 부른다.

✒️ 복잡도의 표기

상기했듯이, 알고리즘의 성능을 평가할 때는 보통 시간 복잡도와 공간 복잡도를 주로 본다. 이 두 개를 공통적으로 표현한다면 다음과 같다.

알고리즘의 주어진 특정 크기의 입력(N)을 기준으로 수행 시간 혹은 사용 공간이 얼마나 되는가.

따라서 이러한 '복잡도'를 단순하고 명료하게 식으로 나타낼 방법이 필요했고, 이를 위한 것이 점근 표기법이라는 것이다.

1. 점근 표기법 (Asymptotic Notation)

점근 표기법이란 간단하게 말해서 입력 N의 크기가 충분히 클 때, 어떤 항이 지배적인지를 표현하는 방법이다. 이를 통해 수행 시간이나 사용 공간을 대략적으로 수식을 통해 표현할 수 있다.

이러한 점근 표기법에는 크게 세 가지 방법이 존재한다.

  1. 빅-Ω 표기법 (Big-Omega Notation)
    • 성능의 하한을 기준으로 하는 표기법이다. 즉, 가장 '최선'일 때를 기준으로 성능을 표기하는 방식이다.
  2. 빅-Θ 표기법 (Big-Theta Notation)
    • 성능의 평균을 기준으로 하는 표기법이다. 즉, 가장 일반적인 상황을 기준으로 성능을 표기하는 방식이다.
  3. 빅-O 표기법 (Big-O Notation)
    • 성능의 상한을 기준으로 하는 표기법이다. 즉, 가장 '최악'일 때를 기준으로 성능을 표기하는 방식이다.

이 중에서 보통 우리가 복잡도를 표기할 때 쓰는 표기법은 빅-O 표기법이다.

빅-O 표기법 최악의 경우를 상정한 표기법이기 때문에, 절대로 이 이상으로 성능이 나빠질 수 없다는 안전한 보장을 해준다.

2. 빅-O 표기법 (Big-O Notation)

그럼 이제 이 빅-O 표기법이라는 것을 어떻게 만드는지를 알아보자.

기본적으로 O (증가 함수)와 괄호로 표기를 하고, 이 증가 함수란 데이터의 크기에 대해 알고리즘의 수행 시간 및 공간이 늘어나는 비율을 함수로 나타낸 것이라고 보면 된다. 그리고 괄호 안에는 규칙에 따라 현재 알고리즘에 맞는 수식을 넣기 되는데, 이는 의외로 간단하다. 단순하게 말하자면 기본적으로 다음과 같은 규칙을 따르면 된다.

상수항을 무시하고, 영향력이 없는 항을 무시한다.

하지만 이렇게 말하면 너무 추상적이니, 좀 더 자세히 설명하면 다음과 같다.

  1. 상수항을 제거한다.
    • O(2N)이라면 O(N)으로 표기한다.
  2. 가장 큰 항만 남긴다.
    • O(N² + N)이라면 O(N²)으로 표기한다.
  3. 순차 실행은 덧셈한다.
    • A가 O(N)이고 B가 O(N²)일 때, 전체는 O(N + N²) = O(N²)이다.
  4. 중첩 루프는 곱셈한다.
    • 바깥 루프가 N번 반복이고 안쪽 루프가 M번 반복이라면 O(NM)이다.
  5. 일정 비율로 줄어드는 반복은 로그이다.
    • while(n > 0) { n /= 2; } 처럼 일정 비율로 줄어든다면, O(logN)이다.

⏱️ 시간 복잡도 (Time Complexity)

시간 복잡도란?

입력 크기 N이 커질수록 실행 시간이 어떻게 커지는가.

즉, 간단히 말하자면 이 알고리즘의 실행 시간이 얼마나 걸리냐를 보는 것이다.

이론적으로 공간 복잡도의 상한이 시간 복잡도이기 때문에, 복잡도를 말한다면 일반적으로 이 시간 복잡도를 말하는 것이다.

기본적으로 속도는 다음과 같이 정렬된다.

\[O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(N^3) < O(C^N)\]

각각의 경우에 대해 대표적인 예들을 보자면 다음과 같다.

  • O(1) - 상수 시간
    • 해시 테이블
  • O(log N) - 로그 시간
    • 이진 탐색
  • O(N) - 선형 시간
    • 순차 탐색
  • O(N log N) - 선형 로그 시간
    • 합병 정렬, 퀵 정렬
  • O(N²) - 2차 시간
    • 버블 정렬, 선택 정렬, 삽입 정렬
  • O(N³) - 3차 시간
    • 플로이드 워셜 알고리즘
  • O(C²) - 지수 시간
    • 하노이의 탑

따라서 상수 시간에 가까운 알고리즘일수록 성능이 좋다고 보면 된다.

📦 공간 복잡도 (Space Complexity)

공간 복잡도란?

입력 크기 N이 커질수록 추가 메모리가 어떻게 커지는가.

즉, 간단히 말하자면 이 알고리즘를 실행하는데 필요한 메모리가 얼마나 되냐를 보는 것이다. 만약 N의 길이의 배열이 이중 구조로 되어 있다면, 공간 복잡도는 O(N²)이 된다.

일반적으로 현대에 들어서는 하드웨어의 성능이 매우 좋아졌기에 용량의 부족함이 많이 사라졌기에, 공간 복잡도의 중요성이 떨어졌다. 하지만 불필요한 메모리 공간 할당은 있으면 좋을게 없으므로, 시간 복잡도보다는 아니지만 항상 신경을 써주도록 하자.

⚙️ 기타 성능 요소

위와 같은 방식으로 시간 복잡도와 공간 복잡도로 성능을 표기할 수 있는데, 이상하게도 같은 O(N)임에도 어떤 로직은 더 빠르고, 어떤 건 더 느리고 하는 등의 성능 차이가 나는 때가 빈번하다. 이러한 차이가 발생하는 이유는 여러 요소들이 존재한다.

  1. 상수 계수
    • 비싼 연산 (해싱, 비교 함수, 문자열 비교 등)이나 루프 내의 로직이 무거운 경우 상수 계수가 커지고, 성능은 떨어진다.
  2. 메모리 접근 패턴 (캐시)
    • vector 같은 연속 메모리 구조는 캐시 친화적이므로 빠르고, list 등의 노드 기반 메모리 구조는 캐시 미스가 많아 느리다.
  3. 동적 할당 빈도
    • new / delete 등의 동적 할당 / 해제나 컨테이너의 재할당 등이 잦으면 오버헤드로 인해 느려진다.
  4. I/O
    • cin / cout등의 입출력은 생각보다 내부 작업이 무거워 많이 반복되면 성능이 떨어진다.

이외에도 여러 요소들이 복합적으로 작용하며, 보이는 성능보다 실제 성능을 떨어트리는 결과를 낳게 된다. 이러한 요소들까지 신경을 써가며 로직을 구현하면, 의도한 속도에 가까워질 수 있을 것이다.

💭 그 외

물론 평소에 어떤 기능을 구현하거나 프로그램을 만드는 때에도 이러한 성능을 생각하면 좋지만, 가장 많이 써먹는 때는 코딩 테스트 때 같다. 확실히 이게 맞겠다 싶어서 막 구현을 하고 뒤늦게 시간 초과나 메모리 초과가 나오는 것보다, 미리 어느 정도 시간 복잡도와 공간 복잡도를 가늠하고 알고리즘을 생각해서 푸는게 굉장히 도움이 많이 된 것 같다.

🔗 참고자료

Comments

Related Posts