1. 차수란?
앞선 글에서 0.001\(n^{2}\)보다 100\(n\)이 궁극적으로 더 빠른 알고리즘이라고 말씀드렸습니다.
왜일까요? 100n은 1차식으로 증가하는 반면, 0.001\(n^{2}\)은 2차식으로 증가하기 때문에 증가율이 더 높습니다.
이렇게 알고리즘의 효율성을 비교하기 위해서는 앞에 붙은 계수보다는 차수가 더 중요합니다.
극단적인 예로 100000000000000000000\(n\)이 0.00000000000001\(n^{2}\)보다 더 빠르다고 설명할 수 있습니다.
이때, 100\(n\)은 1차시간 알고리즘, 0.001\(n^{2}\)은 2차시간 알고리즘이라고 설명할 수 있겠습니다.
5\(n^2\) +100 같은 함수는 순수 2차함수라고 할 수 있습니다.
그에 반해 0.1\(n^2\)+ \(n\) + 100 같은 함수는 1차항이 있기 때문에 완전 2차함수라고 합니다.
완전 2차함수도 궁극적으로 보면 결국 2차 항이 이 함수를 지배합니다.
아래의 표를 참고하세요.
| \(n\) | 0.1\(n^2\) | 0.1\(n^2\) + \(n\) + 100 |
| 10 | 10 | 120 |
| 20 | 40 | 160 |
| 50 | 250 | 400 |
| 100 | 1,000 | 1,200 |
| 1,000 | 100,000 | 101,100 |
그로므로 비록 함수가 완전 2차함수 일지라도 순수 2차함수로 분류할 수있습니다.
즉, 알고리즘의 시간복잡도가 2차함수면 2차시간 알고리즘이라고 할수 있습니다.
따라서 복잡도 함수를 분류할 때, 낮은 차수의 항들은 항상 버릴 수있습니다.
2. 점근적 표기법 (Asymptotic Notations : \(O, \Theta, \Omega \))
점근적 표기법은 앞에서 했던 time complexity들의 함수를 카테고리화 시키는 표기법이라고 이해하시면 됩니다.
어떤 알고리즘의 시간 복잡도 함수가 \(n^2+10\)이라면 이 알고리즘은 \(\Theta(n^2)\)에 속하게 됩니다.
\(\Theta\)
먼저 \(\Theta\)(Theta)에 대해 설명드리겠습니다.
순수 2차 함수로 분류되는 함수는 \(\Theta(n^2)\)으로 표현할 수 있습니다.
만약 어떤 함수가 \(\Theta(n^2)\)에 속한다면 이 함수의 차수는 \(n^2\)이고, 2차 시간 알고리즘으로 분류됩니다.
마찬가지로 순수 3차 함수로 분류되는 함수는 \(\Theta(n^3)\)입니다.
흔한 복잡도의 카테고리를 말씀드리겠습니다.
\(\Theta(lg n), \Theta(n), \Theta(n lg n), \Theta(n^2), \Theta(n^3), \Theta(2^n)\)
이렇게 카테고리가 있습니다.
이렇게 보시다시피 왼쪽부터 차레대로 \(2^n\), \(n^3\), \(n^2\), \(nlg n\), \(n\), \(lg n\) 입니다.
지수시간이 아니더라도 쓸모있다고 생각하실 수 있는데, 2차 시간 알고리즘도 크기가 10억인 입력을 실행하는데 31년이 걸립니다.
하지만 \(\Theta(n lg n)\) 알고리즘은 같은 입력에 대해 30초만 걸리죠.
이처럼 지수 시간이 낮아야 좋지만, 그렇다고 꼭 높은 차수가 안 좋다는건아닙니다.
더 높은 시간 복잡도를 가지는 알고리즘도 실제로 많이 씁니다.
아무튼 시간을 정확히 측정할 수 없으므로, 비교를 하기 위해서는 최고 차항의 차수에 대해 비교를 합니다.
이때, 이 함수의 최고 차항의 차수를 \(\Theta(x)\)라고 표현합니다.
\(O\)
\(O\)는 big O라고 부릅니다.
정의)
주어진 복잡도 함수 \(f(n)\)에 대해서 \(O(f(n))\)은 정수 N 이상의 모든 n에 대해서 다음 부등식이 성립하는 양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 \(g(n)\)에 대한 집합이다.
\(g(n) \,\leq\, c \times f(n)\)
이해가 되시나요?
만약 \(g(n) \,\epsilon\, O(f(n))\) 이면 \(g(n)\)은 \(f(n)\)의 큰 \(O\)이다 라고 합니다.
예를 들어서, \(n^2+10n \leq 2n^2\) 이라고 했을 때, 처음에는 비록 \(2n^2\) 위에 있지만, 궁극적으론 \(2n^2\)의 아래에 위치하게 됩니다.
이때, 우리는 \(n^2 + 10n \, \epsilon \, O(n^2)\) 이라고 합니다.
참고로 \(g(n)\)이 \(n^2+10n\)입니다.
만약 \(g(n)\)이 \(O(n^2)\) 이면, \(g(n)\)은 궁극적으로 어떤 순수 2차 함수인 \(cn^2\) 아래에 놓이게 된다는 뜻입니다.
이는 곧 \(g(n)\)이 어떤 알고리즘의 시간복잡도라면, 이 알고리즘은 궁극적으로 빠르기가 최소한 2차 함수만큼은 된다는 뜻입니다.
그러면 \(g(n)\, =\, n + 1\)이라면 \(g(n)\)도 \(O(n^2)\)에 속할까요? 한 번 생각해보세요
아무튼 big "oh"는 항상 함수의 궁극적인 상태를 고려하기 때문에 함수의 점근적인(asymptotic) 상태라고 합니다.
big "oh"는 함수의 점근적인 상한을 정한다 라고 합니다.
보통은 이 big "oh"가 알고리즘의 효율성을 비교할 때 가장 유용하게 쓰입니다.
앞 글에서 설명드렸던 worst-case를 점근적 표기법으로 표시한 것이 바로 이 big "oh"입니다.
아무리 느려도, 아무리 안 좋아도 \(O(x)\)보다는 빠르거든요.
\(\Omega\)
\(\Omega\)(Omega)는 점근적인 하한입니다.
어떤 알고리즘이 아무리 빨라도 이 최소한 이 \(\Omega\)보다는 느리거나 같습니다.
정의)
주어진 복잡도 함수 \(f(n)\)에 대해서 \(O(f(n))\)은 정수 N 이상의 모든 n에 대해서 다음 부등식이 성립하는 양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 \(g(n)\)에 대한 집합이다.
\(g(n) \,\geq \,c \times f(n)\)
위의 big "oh"를 제대로 이해하셨다면 "omega"는 별 설명 없어도 충분히 이해하실겁니다 !
보통 "Omega"는 문제의 시간 복잡도를 쓰는데 사용합니다.
이게 무슨 소리냐면 알고리즘의 시간 복잡도를 파악할 때는 \(O(x)\)를 쓰지만, 이 문제 자체의 시간 복잡도를 파악하기 위해서는 \(\Omega(x)\)를 사용합니다.
이 문제를 아무리 빠르게 풀려고해도, 어떤 좋은 알고리즘을 쓰더라도, 결국 \(\Omega(x)\)보다는 느리다는 뜻으로 사용하기 때문에 문제의 시간 복잡도를 표현할 때 사용합니다.
문제와 시간 복잡도와 알고리즘의 시간 복잡도는 엄연히 다릅니다!!
차수의 특성
앞서 "Theta"가 함수의 차수를 결정한다고 했습니다.
이때 특성이 있는데요. 한 번 알아보겠습니다.
\(\Theta\)의 정리)
주어진 복잡도 함수 \(f(n)\)에 대해서 다음과 같이 정의한다.
\(\Theta(f(n))\, = \,O(f(n)) \,\cap\, \Omega(f(n))\)
\(\Theta(f(n))\)은 N 이상의 모든 정수 n에 대해서 다음 부등식을 만족하는 양의 실수 c, d와 음이 아닌 정수 N이 존재하는 복잡도 함수 \(g(n))\)의 집합이다.
\(c \times f(n)\, \leq \,g(n)\, \leq \,d \times f(n)\)
입니다.
만약 \(g(n) \,\epsilon\, \Theta(f(n))\)이면, "\(g(n)\)은 \(f(n))\)의 차수(degree)이다" 라고 합니다.
이때, big "oh"나 \(\Omega\)로도 충분히 차수를 표현할 수 있지 않나? 라고 생각하실 수 있습니다.
예를 들어보겠습니다.
함수 \(n+7\)은 \(O(n^2)\)에 속합니다. 왜냐면 \(n\,+\,7\)은 아무리 느려봤자 \(n^2\)보다는 빠릅니다.
또 다른 함수 \(4n^3+3n^2\)은 \(\Omega(n^2)\)에 속합니다. 아무리 빨라져도 \(n^2\)보다는 느립니다.
하지만 그렇다고 이 두 함수의 최고 차수가 \(n^2\)는 아닙니다.
따라서 함수의 제대로 된 차수에 대해서 알기 위해서는 \(\Theta(x)\)를 통해야만 제대로 된 차수에 대해 알 수 있습니다.
다항 시간 알고리즘은 일반적으로 efficient algorithm이라고 합니다.
지수 시간 알고리즘은 일반적으로 inefficient algorithm이라고 합니다. 풀기 난해하다는 뜻입니다.
따라서 어떤 문제의 난이도에 대해 알고싶다면 우선적으로 시간 복잡도를 파악해야 합니다.
3. 결론 및 요약
알고리즘은 문제 해결 절차입니다. 어떤 문제를 해결하기 위한 단계적 절차라고 할 수 있습니다.
하나의 문제에 다양한 알고리즘이 있고, 자원은 한정적이기에 저희는 보다 효율적인 알고리즘을 선택해야합니다.
이때, 알고리즘을 분석하기 위해선 정확도 분석과 효율성 분석이 있습니다. 정확도 분석은 대학생 수준이 아니기 때문에 패스합니다. 따라서 효율성 분석으로 알고리즘을 분석합니다.
알고리즘의 효율성에는 공간 효율성과 시간 효율성이 있습니다. 일반적으로 공간 효율성보다는 시간 효율성을 더 중요시 여깁니다.
이때, 실제 시간을 측정하기엔 너무나 의존적인 요소가 많기에 저희는 basic operation이 input size에 따라 해당 basic operation이 얼마나 복잡한지를 측정합니다. 즉 연산의 복잡도를 측정합니다.
여기서 쓰이는 요소가 every-case time complexity, worst-case time complexity, best-case time complexity, average-time complexity가 있습니다.
n (input size)에 대한 다양한 식이 나올텐데, 우리는 이를 좀 더 간략화하기 위해서 점근적 표기법(Asymptotic Notations)을 사용합니다.
\(\Theta\)는 n에 대한 함수(= \(g(n)\)이라 하겠습니다)의 차수이고,
\(O(f(n))\)는 \(g(n)\)이 아무리 느려도 궁극적으로 \(c \times f(n)\)보다는 빠르다는 뜻입니다.
\(\Omega(f(n))\)은 \(g(n)\)이 아무리 빨라도 궁극적으로 \(c \times f(n)\)보다는 느리다는 뜻입니다.
이렇게 저희는 연산의 복잡도를 함수로 만들어서 이를 점근적 표기법으로 표현해 알고리즘의 시간 효율성을 비교합니다.
감사합니다.
다음 글에서부터는 진짜 알고리즘들에 대해 적겠습니다.
지적 환영합니다.
출처 : 알고리즘 기초, 대학교 강의