증가 기준

증가 기준(Order of Growth)¶

여러줍니 두 알고리즘을 분석하고 그들의 실행시간을 입력의 크기에 대한 함수로 표현했다고 치자. 알고리즘 A는 $100n+1$번의 단계를 밟아 크기 n인 문제를 풀 수 있고, 알고리즘 B는 $n^2 + n + 1$ 번의 단계를 밟는다.

다음 표는 여러 가지 크기의 문제들에 대해, A와 B의 알고리즘의 실행시간을 보여준다.

입력의 크기	A 알고리즘의 실행시간	B 알고리즘의 실행시간
10	1001	111
100	10001	10101
1000	100001	1001001
10000	1000001	$> 10^1$$^0$

n=10일 때, 알고리즘 A는 별로 좋아 보이지 않는다. 알고리즘 B보다 무려 10배나 긴 시간이 든다. 하지만 n=100인 경우 두 알고리즘의 시간은 유사해지고, 큰 값들일 때는 A가 훨씬 낫다.

이런 결과가 나오는 근본적인 이유는, n의 값이 클 때 $n^2$항을 포함하는 모든 함수는 최고차항이 n인 함수보다 빠르게 증가하기 때문이다. 최고차항은 가장 높은 지수가 붙어있는 항을 일컫는다.

알고리즘 A의 최고차항은 꽤 큰 계수인 100이 붙어있는데, 그렇기 때문에 n이 작을 때 B가 A보다 좋은 성능을 내는 것이다. 하지만 계수와는 상관없이 $an^2 > bn$이 되는 n이 반드시 존재한다.

최고차항이 아닌 항들에 대해서도 동일한 주장이 적용된다. 알고리즘 A가 n+1000000일 때, 실행시간도 마찬가지로 n이 충분히 크다면 알고리즘 B보다 좋다.

일반적으로 최고차항이 낮은 알고리즘이 큰 문제에는 더 좋을 거라고 기대하게 되는데, 작은 문제들에 대해서는 다른 알고리즘의 성능이 더 좋은 교차점이 있을 수도 있다. 교차점의 위치는 알고리즘의 세부 사항, 입력 그리고 하드웨어에 따라 달라지며 다라서 알고리즘 분석이라는 목적 하에서는 일반적으로 무시된다. 하지만 염두에 두고는 있어야 한다.

만약 두 알고리즘의 최고 차항이 동일하다면 어느 것이 더 좋다고 판단하기가 어렵다. 다시 말하지만, 정답은 세부 조건에 따라 다르다. 그래서 알고리즘 분석을 할 때는 동일한 최고차항을 가진 함수들은 계수가 다르더라도 등가로 취급한다.

하나의 증가 기준이란 각 함수의 점근적인 증가 형태가 등가로 취급되는 함수들의 집합이다. 예를 들어 2n, 100n 그리고 n+1은 동일한 증가 기준에 속한다. 이 기준은 빅오 표기법에 따르면 O(n)으로 표현하며, 이 집합에 속한 모든 함수가 n에 대해 선형으로 증가하기 때문에 선형이라고도 부른다.

최고차항이 $n^2$인 모든 함수는 $O(n^2)$에 속한다. 이처럼 최고차항이 $n^2$인 함수를 이차함수라고 한다.

다음 표는 알고리즘 분석에 가장 자주 나오는 증가 기준들이다. 표의 뒤로 갈수록 효율이 나쁘다.

증 가 이름	기준이름
O(1)	상수
O(logbn)	로그(모든 b에 대해서)
O(n)	선형
O(nlogbn)	n 로그n
$O(n^2)$	이차
$O(n^3)$	삼차
$O(c^n)$	지수(모든 c에 대해서)

로그 항의 경우, 로그의 밑은 관계가 없다. 로그의 밑을 바꾸는 것은 상수를 곱하는 것과 마찬가지로 증가 기준을 변화시키지 않는다. 이와 유사하게, 모든 지수 함수는 지수의 밑과 관계없이 동일한 증가 기준에 속한다. 지수 함수들은 굉장히 빠르게 증가하며, 따라서 지수 함수로 된 알고리즘은 작은 문제에만 적합하다.

성능을 중요시하는 프로그래머들은 간혹 이런 종류의 분석을 받아들이기 어려워한다. 그들의 말도 일리는 있다. 때로 상수와 최고차항이 아닌 항들도 큰 차이를 만들 수 있고, 하드웨어의 상황과 프로그래밍 언어, 입력의 특성도 큰 차이를 만든다. 또한 작은 문제들의 경우, 점근적 행태는 그다지 관계가 없다.

하지만 여러분이 이 같은 주의사항을 숙지한다면, 알고리즘 분석은 유용한 도구가 될 수 있다. 적어도 큰 문제에 대해서 '더 나은; 알고리즘은 대개 더 좋고, 때로는 훨씬 더 좋다. 동일한 증가 기준을 가진 두 알고리즘의 차이는 대개 상수 인자이다. 그리고 좋은 알고리즘과 나쁜 알고리즘의 차이는 딱 정해진 것이 아니다.

이미지 출처 : https://joshuajangblog.wordpress.com/2016/09/21/time_complexity_big_o_in_easy_explanation/

내용 출처 : 복잡계와 데이터 과학