[ Algorithm ] 알고리즘 효율 (2)
알고리즘
4. 차수
첫째 알고리즘의 일정 시간 복잡도는 $100n$, 둘째 알고리즘의 일정 시간 복잡도 $0.01n^2$ 이라고 가정했을 때 첫째 알고리즘이 둘째보다 궁극적으로 빠르다. 두 알고리즘에서 설정한 단위 연산 1회 실행 시간이 같고, 주변 명령문 실행 시간도 거의 같은 경우 n값에 대해서만 첫째 알고리즘이 빠르다고 할 수 있다.
1차 시간 알고리즘(linear-time algorithm) : 시간 복잡도가 입력 크기 $n$에 대해 1차 함수 (ex) 시간 복잡도가 $n$과 $100n$인 알고리즘)
- 2차 시간 알고리즘(quadratic-time algorithm) : 알고리즘 시간 복잡도가 입력 크기 $n$에 대해 2차 함수 (ex) 시간 복잡도가 $1n^2$과 $0.01n^2$인 알고리즘)
- 순수 2차 함수(pure quadratic function) : ex) 1차항이 없는 $5n^2$ 과 $5n^2 +100$
- 완전 2차 함수(complete quadratifuction) : ex) 1차항이 있는 $0.1n^2 + n +100$
- $Θ$ : 쎄타(theta), 순수 함수로 분류되는 복잡도 함수의 집합
- 어떤 함수가 $Θ(n^2 )$ 집합의 원소라면 그 함수의 차수가 $n^2$ ,낮은 차수의 항은 버릴 수 있으므로, $g(n)$의 차수는 $n^2$이다.
- 어떤 알고리즘의 시간 복잡도가 $Θ(n^2 )$에 속하면 그 알고리즘을 2차 시간 알고리즘 또는 $Θ(n^2 )$ 알고리즘이라고 한다.(“그 알고리즘은 $Θ(n^2 )$이다.”)
- 순수 3차 함수로 분류될 수 있는 복잡도 함수의 집합은 $Θ(n^3 )$이고, 이 집합의 함수는 차수가 $n^3$ 이다.(2차 함수와 비슷하게 정의)
- 복잡도 카테고리(complexity categories) : 시간 복잡도의 최고차항의 상수를 무시하고 표시하는 것.
1) 큰 O (big O)
주어진 복잡도 함수 $f(n)$에 대해서 $O(f(n))$은 정수 $N$ 이상의 모든 $n$에 대해서 다음 부등식이 성립하는 양의 실수 $c$와 음이 아닌 정수 $N$이 존재하는 복잡도 함수 $g(n)$의 집합이다. => $g(n) ≤ 𝐶×𝑓(𝑛)$
“$g(n)$”∈”$O(f(n))$” 이면 “$g(n)$은 $f(n)$의 큰 $O$이다.”
$g(n)$이 $O(n^2 )$이면, $g(n)$은 궁극적으로 그래프 상에서 어떤 순수 2차 함수 $cn^2$ 아래 놓이게 된다.
만약 $g(n)$이 어떤 알고리즘의 시간 복잡도라면, 그 알고리즘의 실행시간은 궁극적으로 빠르기가 최소한 2차 함수만큼은 된다는 뜻이며, 분석에 사용할 때 $g(n)$은 궁극적으로 최소한 순수 2차 함수만큼 좋다고 할 수 있다.
“큰 O”는 함수의 궁극적인 상태만 고려하기 때문에 함수의 점근적인(asymptotic) 상태를 나타낸다고하며, 함수의 점근적인 상한(asymptotic upper bound)을 정한다고 한다.
복잡도 함수가 $O(n^2 )$에 속하기 위해 굳이 2차함수 일 필요가 없으며, 그래프 상에서 궁극적으로 순수 2차 함수 아래에 놓이기만 하면 된다. -> 어떤 대수(logarithm)함수나 1차 함수도 $O(n^2 )$에 속한다.
2) Ω 오메가(omega)
주어진 복잡도 $f(n)$에 대해서 $Ω(f(n))$은 $N$이상의 모든 $n$에 대해서 다음 부등식을 만족하는 양의 실수 $c$와 음이 아닌 정수 $N$이 존재하는 복잡도 함수 $g(n)$의 집합이다. => $g(n)≥ C×f(n)$
점근적인 하한(asymptotic lower bound)을 정한다.
“$g(n)∈Ω(f(n)$”이면,“$g(n)은 f(n)$의 오메가이다.”
$g(n)$이 $Ω(n^2 )$ 에 속하면 $g(n)$은 궁극적으로 그래프 상에서 어떤 순수 2차 함수 위에 놓이게 된다. 즉, $g(n)$은 “궁극적으로 최소한 순수 2차 함수만큼은 나쁘다.”
어떤 함수가 $O(n^2 )$와 $Ω(n^2 )$ 모두 속한다면, 궁극적으로 이 함수는 그래프에서 어떤 순수2차 함수 아래에 위치하게 됨과 동시에 또다른 어떤 순수 2차 함수만큼 좋고, 또다른 어떤 순수 2차 함수만큼 나쁘다.
3) 차수(order)
주어진 복잡도 $f(n)$에 대해서 $Θ(f(n)) = O(f(n)) ∩ Ω(f(n))$라 정의하며, $Θ(f(n))$는 $N$이상의 모든 정수 $n$에 대해서 다음 부등식이 만족하는 양의 실수 $c$, $d$와 음이 아닌 정수 $N$이 존재하는 복잡도 함수 $g(n)$의 집합이다. => $c ×f(n) ≤ g(n) ≤d×f(n)$
- “$g(n)$”∈”$O(f(n))$” 이면 “$g(n)$은 $f(n)$의 차수(order)이다.”
4) 작은 o(small o)
주어진 복잡도 함수 $f(n)$에 대해서 $o(f(n))$은 모든 양의 실수 $c$에 대해서 $n ≥ N$을 만족하는 모든 $n$에 대해서 다음 부등식을 만족하는 음이 아닌 정수 $N$이 존재하는 모든 복잡도 함수 $g(n)$의 집합이다. => $g(n) ≤c×f(n)$
“$g(n)$”∈”$o(f(n))$” 이면 “$g(n)$은 $f(n)$의 작은 o(small o)이다.”
“큰 오(big O)”는 그 범위가 성립하는 “어떤” 양의 실수 $c$ 가 반드시 존재한다는 것을 의미, 이는 “모든“ 양의 실수 $c$에 대해서 그 범위가 성립해야 하며, 범위가 모든 양수 $c$에 대해 성립하므로, 임의로 작은 $c$에 대해 성립한다.
$g(n)∈o(f(n)$이면, $n ≥ N$을 만족하는 모든 $n$에 대해서 다음 부등식을 만족하는 $N$이 존재한다면, $n ≥ N$을 만족하는 모든 $n$에 대해서 “$g(n)$” ≤0.00001×$f(n)$을 만족하는 $N$이 존재한다.
$n$이 커지게 되면, $g(n)$은 $f(n)$에 비해 하찮을 만큼 작아지게 되며, 분석의 관점에서 $g(n)$이 $o(f(n))$이면, $g(n)$은 $f(n)$ 같은 함수보다 궁극적으로 좋다.
※ 실제로는 특성을 반복 적용하는 대신, 낮은 차수를 가진 항을 그냥 버리면 된다고 단순히 생각하면 쉽다.
만약 알고리즘의 정확한 시간복잡도를 구할 수 있다면, 단순히 낮은 차수를 버려서 차수를 결정할 수 있다. 정확한 차수를 구할 수 없을 때는, “큰 오＂나 “오메가“를 쓴다.
어떤 알고리즘의 $T(n)$ 또는 $W(n)$ 등을 정확하게 결정할 수 없다고 가정했을 때 정의를 바로 적용하여 $T(n)∈O(f(n))$은 $T(n) ∈ Ω(f(n))$과 서로 필요충분조건이라는 것을 증명할 수 있다면, $T(n) ∈ Θ(f(n))$이다.
복잡도를 $f(n)∈ Θ(n^2)$ 대신 $f(n) = Θ(n^2)$ , $f(n)= O(n^2) 대신$, $f(n) = O(n^2)$ 으로도 표현할 수 있다.
※ 극한을 사용하여 차수를 결정
차수를 결정하는데 극한(limit)을 사용할 수도 있는데 이를 위해선 극한과 미분에 대한 이해 필요
- 로피탈의 규칙(L’Hopital’s Rule)
출처: 알고리즘 기초