Big-O Notation (빅오 표기법)
개요
Big-O 표기법이란 “알고리즘의 성능을 입력 크기에 따라 최악의 성능을 나타내는 수학적 표기법” 이다.
프로그램의 성능 측정 방법론
효율적인 프로그램은 어떤 기준을 참고로 삼아야하는가에 대한 기준을 이야기해보고자 한다.
결국 컴퓨터는 연산을 위한 기기로서, 데이터를 처리하는데 있어서 연산 횟수와 문제 상황에 맞는 접근 방식으로 이 연산을 최적화할 필요가 있다.
연산 횟수를 줄이기 위해 메모리, 즉 다른 저장 장소를 사용하는 경우가 있다.
혹은 저장되는 자료를 필요한 만큼만 저장하여 컴퓨터 연산을 줄이거나 혹은 컴퓨터의 저장으로 소모되는 비용들을 줄이는 방법이 요구된다.
가령, 1TB 데이터를 잘 저장해서 필요한 만큼 선별하던 뭘 하던 100GB로만 만들어도 비용은 줄어드니까 말이다.
따라서, 프로그램은 기본적으로 두 가지에 의해서 성능이 측정된다.
•
시간 복잡도 : 알고리즘에 사용되는 연산 횟수
•
공간 복잡도: 알고리즘에 사용되는 메모리 양
다만 알고리즘 문제를 푸는데 있어서 공간 복잡도 보단 시간 복잡도가 우선적으로 고려하는 것으로 보인다.
대부분 실행시간에서 기준치를 못넘겨서 문제를 틀리는 경우가 많기 때문이다.
한편, 메모리를 조금 사용하더라도 시간 복잡도를 크게 줄일 수 있는 방법이 있기도 하다.
대표적으로 Dinamic Programming이라는 알고리즘은 메모리를 사용해서 시간 복잡도를 줄이는 방법을 사용한다.
Big-O 표기법
그렇다면 Big-O 표기법이란 무엇일까?
위에서 언급한 시간 복잡도나 공간 복잡도를 나타내는 수학적 표기법이다.
입력 데이터를 이라는 변수로 생각하고, 함수 내에 연산 횟수를 표기한다.
입력 데이터 n개에 대해서 n번의 연산을 하게 된다면 아래와 같다.
그런데 정말 중요한 것은 최악의 성능을 표기한다는 것이다.
즉, 최악의 상황에서 가장 많은 연산을 하게 됐을 때를 총 연산횟수로 산정하여 나타낸다는 것이다.
입력데이터가 알고리즘에 최적화되지 않게 들어와서, 알고리즘의 연산이 최대치로 갔을 때를 나타내야만 한다.
그도 그럴 것이. 보통 성능이라고 하면 좋은 성능만을 고려해서 어떤 시스템을 만들면 최악의 상황에 대응이 안되지 않겠는가. 어찌 보면 프로그램을 개발하는 입장에서는 당연한 접근 방식일 것이다.
만약 입력 데이터가 이며 시간 복잡도가 인 알고리즘의 연산 횟수는 최악의 경우 총 의 연산을 수행하게 된다.
한편 알고리즘 채점을 위해서 쓰이는 CPU 성능을 고려해서 아래의 식으로 산출하기도 한다.
•
1초당 약 1억번의 연산을 한다.
알고리즘을 풀 때 이 점을 반드시 고려해야한다.
•
예를 들어, 알고리즘 시간 제한이 2초라면 2억번 연산만 허용되므로, 입력 데이터가 10만번일 때, 시간복잡도가 인 알고리즘은 총 100억번의 연산을 하므로, 이 알고리즘을 사용할 수가 없게 된다.
우리가 아래와 같은 반복문에 대한 코드를 짰다고 생각해보자.
for k in range(0, n):
for i in range(0, k):
# ... 어떠한 처리과정
return something
Python
복사
위 반복문의 빅오 표기는 얼마일까?
당연히 이다. 이 간단한 알고리즘은 이중 반복이니까 n 개의 데이터를 n번 처리한다.
보통 자주 사용하는 알고리즘들은 이미 잘 알려진 빅오표기들이 존재한다. 이중 반복문은 등등… 이것들을 외워두는 것도 분명 도움이 될 것이다.
빅오 표기법은 정말 기초중에 기초인 개념으로, 추후 정렬 알고리즘이나 다른 알고리즘의 성능을 표시하는데 있어서 반드시 알고 가자.
REFERENCES
Written by Changyu Lee, 2024-10-11