Big-O 표기법

Big-O 표기법

프로그래머들은 알고리즘이나 코드가 어떤 성능을 가지는지 설명할 때 Big-O 표기법 을 이용한다. 이번에는 가능한 수학을 사용하지 않으면서 알고리즘 복잡도 분석과 Big-O 표기법에 대해 설명한다.

Big-O표기법은 절대적인 성능이 아니라 상대적인 성능을 나타낸다. 예를들어 이 함수는 300밀리초 안에 작업을 완료한다고 하지 않고, 작업 대상 데이터 크기가 커질 때 소요시간에 따라서 커지는 비율이 어떻게 달라지는지 이야깋 ㅏㄴ다.
작업대상 데이터란 정렬할 숫자의 개수, 해시 맵에서 항목을 찾을 때 해시에 이미 들어있는 데이터의 개수, 파일으 ㄹ복사할 때 파일의 개수 따위를 말한다.

Big-O 표기법은 입력 데이터가 존재하고 그 크기가 가변적인 알고리즘을 대상으로 한다. 입력 데이터가 없거나 실행 소요 시간이 무작위(random) 알고리즘은 Big-O 표기법을 적용할 수 없다.

좀더 형식적으로 말하면 Big-O 표기법은 알고리즘의 실행 소요 시간을 입력 데이터의 크기에 대한 함수로 나타낸 것으로 알고리즘 복자볻 라고도 한다. 어려워 보이지만 실상은 그렇지 않다. 예를들어 어떤 정렬 알고리즘이 500개 항목을 정력하는데 2초가 소요되고 1,000개 항목을 정렬하는 데는 4초가 소요된다고 하자, 데이터가 두 배로 늘어날 때 소요시간도 두배로 늘어났다.

따라서 실행시간은 입력크기에 선형으로 비례하는 함수라고 할 수 있다. 성능과 입력 데이터 크기를 각각 축으로 하여 그래프를 그리면 기울어진 일직선이 나온다.

이러한 경우를 Big-O표기법으로 나타내면 O(n)과 같이 표현된다. 여기서 O는 Big-O 표기법 이라는 것을 나타내고, n은 입력 데이터 크기를 나타낸다. O(n)은 알고리즘의 실행 소요 시간이 입력 데이터의 크기에 정비례하는 함수임을 표현한다.
만약 모든 알고리즘이 위에서처럼 입력 데이터 크기에 비례하는 실행시간을 보여준다면, 컴퓨터 프로그램이 지금보다 훨씬 더 빨가질 것 이다. O(n)은 사실 달성하기 쉽지 않은 성능이다.

 

알고리즘 복잡도	Big-O표기볍	설명	알고리즘 예
상수 (Constant)	O(1)	대상 데이터 크기와 관계없이 항상 수행시간이 동일	배열 항목 하나에 인덱스 값으로 접근
로그 (Logarithmic)	O(log n)	입력 데이터 크기에 따라 실행 시간이 지수 2의 로그 함수에 비례	이미 정렬된 리스트에서 바이너리 탐색으로 특정 항목 탐색
선형 (Linear Logarithmic)	O(n log n)	실행 시간이 입력 데이터 크기의 로그값의 선형 곱에 비례	병합 정렬
제곱 (Quadratic)	O(n^2)	실행 시간이 입력 데이터 크기의 제곱에 비례	선택 정렬과 같이 성능이 낮은 알고리즘
지수 (Exponential)	O(2^n)	실행 시간이 입력 데이터 크기의 승수에 비례	외판원 문제 의 최적화

 

절대적인 숫자 대신 입력크기에 대한 상대적인 값으로 성능을 표기하면 다음과 같은 두가지 장점이 있다.

1. 플랫폼에 독립적이다.
   특정 컴퓨터에서 200밀리초의 소요 시간을 가진다는 정보로는 다른 컴퓨터에서 어떻게 나타날지 짐작하는데 별 도움이 안된다. 같은 컴퓨터에서 비교하더라도 부하 상황과 데이터 크기를 완전히 동일하게 맞추어야 의미가 있다. 반면 입력 데이터의 크기 변화에 따른 성능 변화 정보가 있으면 플랫폼과 독립적으로 알고리즘 간 성능을 비교할 수 있다.
2. 성능이 입력 데이터 크기에 대한 함수로 표현되면 모든 종류의 입력 데이터 크기에 대해 실행 성능을 알 수 있다.
   반면 특정 데이터 크기에 대한 실행 시간 측정치는 다른 데이터 크기에서 실행 시간이 어떻게 될지 알려주지 못한다.

 

어떤 때는 Big-O표기법에 통계적인 기댓값을 반영하기도 한다.

이 경우 Big-O 수식은 기대 시간을 나타낸다. 예를 들어 선형 탐색 알고리즘은 종종 O(n/2)이라고 표기된다. 왜냐하면 확률적으로 전체 항목의 절반 정도를 탐색하면 목적하는 항목이 발견되지 떄문이다. O(n/2)보다 더 빨리 찾아지는 경우는 O(n/2)보다 더 오래 걸리는 경우와 서로 상쇄되어 없어진다.