Functions and Relations (함수와 관계)
대부분의 경우, 우리는 함수의 입력값이 증가함에 따라, 결과값이 얼마나 빠르게 변화하는지에 중점을 둔다. 즉, 함수의 변화속도만 알아봐도 충분하다. 그리고 이를 표기하기 위한 기호들을 알아보자
두 함수 \(f(n)\), \(g(n)\)을 정의역이 양의 정수인 두 함수라 하자. 충분히 큰 n에 대해 다음 식을 성립시키는 양의 상수 c가 존재한다고 하면
\[\begin{align*} f(n) \ \leq \ c\mid g(n)\mid \ ,\\ \end{align*}\]함수\(f\)는 기껏해야 함수\(g\)의 차수를 가진다고 한다. 좀 더 쉽게 풀어쓰면, 함수\(f\)가 아무리 커져봐야 함수\(g\)의 규모와 같거나 작다는 말이다. 또한 이를 다음과 같이 표현할 수 있다.
\[\begin{align*} f(n) = O(g(n))\\ \end{align*}\]만약 다음 식이 성립한다면,
\[\begin{align*} \mid f(n)\mid \ \geq \ c\mid g(n)\mid \ .\\ \end{align*}\]\(f\)는 적어도 \(g\)의 규모를 가진다고 한다. 좀 더 쉽게 풀어쓰면 함수\(f\)는 아무리 못 커도 함수\(g\)의 규모보다는 같거나 크다는 말이다. 또한 이를 다음과 같이 표현할 수 있다.
\[\begin{align*} f(n) = \Omega (g(n))\\ \end{align*}\]마지막으로, 다음 식을 만족하는 \(c_1\), \(c_2\)가 존재하면
\[\begin{align*} c_1\mid g(n)\mid \ \leq \ \mid f(n)\mid \ \leq \ c_2\mid g(n)\mid \ ,\\ \end{align*}\]함수\(f\)와 함수\(g\)는 같은 차수를 가진다고 하고 다음과 같이 표현한다.
\[\begin{align*} f(n) = \Theta (g(n))\\ \end{align*}\]이처럼 각 함수의 차수를 비교할 때는, 각 함수에서 낮은 차수항들은 무시하고 가장 큰 차수를 갖는 항만 본다.
예를 들어 \(f(x) = x^2 + 7x\)라는 함수가 있다고 하자. \(x\)가 무한으로 증가하면, \(7x\)가 함수의 결과값에 미치는 영향보다, \(x^2\)이 함수의 결과값에 미치는 영향이 더 크다. 다시말해 \(x\)가 무한으로 증가하는 상황에서는 \(f(x) = x^2\)이라고 봐도 무관하다.