알고리즘 성능 평가 방법 - 빅오 표기법

알고리즘의 성능을 어떻게 평가할까? 

알고리즘은 문제를 해결하는 절차, 방법을 의미한다. 

 

그렇다면 어떻게 문제를 해결해야 좋다고 말할 수 있을까? 

바로 문제를 올바르게 해결했는지와 빠르게 해결했는지이다.

그렇기에 코딩테스트에서도 제시된 input을 넣었을 때 예상되는 output을 나타내는지로 정확도를 평가하고 

제시된 시간과 메모리 안에서 값이 산출되는지로 효율성을 평가한다. 

즉, 알고리즘의 실행시간이 짧고 메모리를 적게 사용하는 것이 좋은 알고리즘이라 말할 수 있다. 

 

하지만 알고리즘의 성능을 평가할 때 실행시간을 기준으로 평가하기는 어렵다. 

실행시간이 알고리즘이 돌아가는 환경에 따라서 다르게 나타나기 때문이다. 

알고리즘이 실행되는 하드웨어 성능에 따라 달라질 수 있으며

어떤 프로그래밍 언어를 사용하는 지에 따라서도 달라지고 

입력데이터에 따라서도 다른 결과를 보여준다. 

 

그렇기 때문에 실행시간 대신 사용하는 것이 복잡도라는 개념으로

입력 데이터를 n이라고 했을 때 데이터를 처리하는 절차(step)가 몇 번인가를 나타낸다. 

5번 안에 끝나는 알고리즘이 10번 걸리는 알고리즘보다 더 효율적이라고 말할 수 있기 때문이다. 

복잡도는 공간복잡도와 시간복잡도로 나뉘는데 각 개념은 다음과 같다. 

 

공간복잡도 (=메모리의 효율성)

• 알고리즘 과정에서 얼마나 많은 공간(메모리)을 차지하는가

시간복잡도 (=실행시간의 효율성)

• 알고리즘이 데이터를 처리하는데 얼마나 걸리는가

하드웨어 성능이 발전함에 따라 알고리즘이 돌아가는 메모리가 충분해지면서 
공간복잡도보다 시간복잡도에 초점을 두고 알고리즘을 평가한다고 한다. 

 

시간복잡도를 나타내는 방법, 빅오표기법

빅오표기법이란?

• 알고리즘 성능을 수학적으로 표기한 점근 표기법 중 하나
• 입력 데이터 증가에 따라 실행 시간(연산) 혹은 메모리가 얼마나 빨리 증가되었는지를 포현 
• 알고리즘의 효율성을 평가할 때 최선의 경우(빅 오메가,Ω), 평균적인 경우(빅 세타, Θ), 최악의 경우(빅 오, O)를 표현
• 최악의 경우를 대비해야 하므로 일반적으로 알고리즘 성능 평가에는 빅오표기법을 사용
  • "O(N)이라면 데이터가 증가함에 따라 최대로 걸리는 연산은 데이터 입력 개수만큼일 것" 최악의 상한을 제시
• 알고리즘 성능 차이 비교를 쉽게 하기 위해 가장 영향력이 높은 항인 최고차항만 표시하고 상수(constant)와 계수는 버림
  • O(N+3) ⇒ O(N)
  • O(2) ⇒ O(1)
  • O(2N) ⇒ O(N)

• 시간복잡도 순서
  • O(1) < O(㏒ N) < O(N) < O(N ㏒ N) < O(N²) < O(2ⁿ)
  • 상수 함수 < 로그 함수 < 선형 함수 < 다항 함수 < 지수 함수

 

 

빅오표기법 종류

1. O(1), 상수시간

• 입력되는 데이터의 수에 상관없이 언제나 일정한 속도 반환(동일한 step 수)
• stack의 push, pop, 인덱싱, 큐 삽입/제거

def print_first(lst):
    print(lst[0])

 

2. O(log n), 로그시간

• 입력 데이터 크기가 커질수록 처리 시간이 로그만큼 짧아짐
• 이진탐색
• 데이터가 2배가 되더라도 step은 1밖에 증가하지 않음
• input을 반으로 자르고 중간 앞에 데이터는 안 보기 때문에 처리할 때마다 검색해야 하는 데이터가 줄어듦
• 정렬되지 않은 배열에는 사용 불가

3. O(n), 선형시간

• 데이터 증가에 따라 선형적으로 처리시간이 증가
• 선형탐색, 정렬되지 않은 리스트의 요소 제거
• 데이터가 10개 있으면 10번 데이터를 탐색하고, 20개 있으면 20번 탐색

def print_all(lst): 
    for i in lst: 
        print(i)

 

4. O(n log n), 선형로그시간

• 입력 데이터가 많아질수록 처리 시간이 로그배만큼 증가
• 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)

5. O(N²), 제곱시간

• 입력 데이터가 많아질수록 처리시간이 급수적으로 증가
• 삽입 정렬, 버블 정렬, 선택 정렬, 이중 for 문

6. O(2ⁿ), 지수시간

• 입력 데이터가 많아질수록 처리시간이 기하급수적으로 증가
• 재귀로 구현하는 피보나치