Algorithm Analysis

알고리즘을 설계한 후에는 해당 알고리즘이 얼마나 정확하고 효율적인지 분석해야 한다.

Analysis

1. 정확성
   • 정확한 알고리즘은 유효한 입력이 주어졌을 때 유한 시간 내에 정확한 결과를 생성한다.
   • 수학적 기법을 사용하여 알고리즘이 예상대로 수행되는지 증명하는 과정이다.
   • 보통 널리 사용되는 알고리즘들은 이미 정확성이 검증되었기 때문에 신뢰할 수 있다.
2. 효율성
   1. 공간 복잡도(space complexity)
      • 알고리즘 수행에 필요한 총 메모리의 양으로, 적을수록 좋다.
      • 컴파일 과정에서 고정적으로 결정되는 정적공간 + 실행 과정에서 결정되는 동적공간을 측정한다.
   2. 시간 복잡도(time complexity)
      • 알고리즘의 수행시간으로, 빠를수록 좋다.
      • 각 문장(연산)이 수행되는 횟수의 합으로 측정한다.
        (수행시간은 컴퓨터의 속도나 프로그래밍 언어 등 실행환경에 따라 달라지기 때문에 비객관적)
        
        

---

알고리즘 수행시간에 영향을 미치는 요인

1. 입력 데이터의 크기
   • 입력한 데이터의 크기와 수행시간은 비례한다.
   • 입력 크기 𝑛의 함수 ⨍(𝑛)(일반적으로 다항식)으로 수행시간을 표현한다.
2. 입력되는 데이터의 상태
   • 평균 수행시간
     • 가능한 모든 입력 상태의 수행시간의 평균 또는 가중 평균
     • 현실적으로 모든 입력 상태와 그에 대한 수행시간을 알기 어렵기 때문에 사용 x
   • 최선 수행시간
     • 가능한 모든 입력 상태의 수행시간 중 가장 빠른 시간
     • 입력 데이터가 알고리즘에 가장 적절한 형태로 주어진 경우
     • 항상 최적의 상태라고 가정할 수 없기 때문에 사용 x
   • 최악 수행시간
     • 가능한 모든 입력 상태의 수행시간 중 가장 느린 시간
     • 어떠한 입력이 주어져도 이를 초과하지 않는다는 것을 보장하기 때문에 시간 복잡도의 척도로 사용

Asymptotic Performance

• 입력 크기 𝑛이 무한히 커짐에 따라 결정되는 성능(점근 성능)이다.
• 최고차항만을 이용한 어림값으로 단순화시켜서 성능을 표현하는 방법으로, 식의 증가 추세를 쉽게 파악할 수 있다.
• e.g. ⨍(𝑛) = 𝑎𝑛² + 𝑏𝑛 + 𝑐
  1. 수행시간에 가장 큰 영향을 미치는 최고차항 𝑎𝑛²을 제외하고 모두 무시
  2. 계수 𝑎도 𝑛²에 비해 수행시간에 미치는 영향이 작기 때문에 무시
  3. 입력 크기 𝑛에 대한 시간 복잡도는 𝑛²
• 간단하게 계산하려면 최고차항에 영향을 주는 루프에서 반복 횟수만 조사하면 된다.
  

𝑂(Big-O) Notation

• 점근적 상한(Asymptotic Upper Bound) → 입력이 어떤 상태든 실행시간이 상한을 넘지 않음을 보장
• 최악의 수행시간을 나타내기 때문에 안전한 분석을 위해 가장 많이 사용된다.

Time complexity

표기법	시간	설명	알고리즘
𝑂(1)	상수 시간(Constant Time)	𝑛과 무관하게 일정한 실행시간	리스트 인덱싱
𝑂(log𝑛)	로그 시간(Logarithmic Time)	𝑛이 증가해도 실행시간 증가율이 낮음	이진 탐색
𝑂(𝑛)	선형 시간(Linear Time)	𝑛만큼 실행시간 증가	선형 탐색(주로 반복문)
𝑂(𝑛log𝑛)	로그선형 시간(Linearithmic Time)	효율적인 정렬 알고리즘	퀵 정렬, 병합 정렬
𝑂(𝑛2)	제곱 시간(Quadratic Time)	중첩 반복문을 사용할 때 발생	버블 정렬, 선택 정렬, 완전 탐색(Brute Force)
𝑂(𝑛3)	세제곱 시간 (Cubic Time)	3중 반복문을 사용할 때 발생	플로이드-워셜 알고리즘
𝑂(2𝑛)	지수 시간(Exponential Time)	𝑛이 커질수록 실행시간이 2n 비율로 증가	재귀 호출(피보나치 재귀, 부분 집합 생성)
𝑂(𝑛!)	팩토리얼 시간(Factorial Time)	𝑛이 커질수록 실행시간이 n! 비율로 증가	순열, 조합 문제

(입력 크기 𝑛)

Space complexity

표기법	공간	설명	알고리즘
𝑂(1)	상수 공간(Constant Space)	𝑛과 무관하게 일정한 메모리 사용	상수 개의 변수, 포인터 교환, 투 포인터
𝑂(log𝑛)	로그 공간(Logarithmic Space)	재귀 호출에서 추가 스택 프레임이 log𝑛만큼 필요할 때	이진 탐색(재귀), 힙 정렬
𝑂(𝑛)	선형 공간(Linear Space)	𝑛에 비례하는 메모리 사용	리스트 저장, DFS(재귀), 메모이제이션
𝑂(𝑛2)	제곱 공간(Quadratic Space)	2차원 행렬 저장	그래프 인접 행렬, 플로이드-워셜 알고리즘
𝑂(2𝑛)	지수 공간(Exponential Space)	가능한 모든 경우를 저장해야 할 때	상태 공간 탐색(일부), DP 최적화 문제
𝑂(𝑛!)	팩토리얼 공간(Factorial Space)	모든 순열을 저장해야 할 때	순열 생성(완전 탐색), 외판원 문제

(입력 크기 𝑛)

Ω(Big-Omega) Notation

• 점근적 하한(Asymptotic Lower Bound) → 어떤 입력이 주어지든 이 하한보다 더 빠를 수 없음
• 최선의 수행시간 분석에 자주 사용된다.
  

Θ(Big-theta) Notation

• 동일한 점근적 상한과 하한(Asymptotic Tight Bound) → 점근적 상한과 하한을 동시에 만족하는 경우
• 입력 크기 𝑛이 충분히 커지면 실행시간이 항상 특정 범위(𝑂와 Ω 사이) 안에서 유지됨을 보장한다.

References

1. 이관용·김진욱, 『알고리즘』, 한국방송통신대학교출판문화원, 2024