- 처음인 주제에 열라 어렵다
; 갠적으로 recursive가 젤루 어려움.(일단 제낌);
- 함수의 집합을 나타내는데, 세가지 표현방법이 있다. - Ο, Ω, θ
- Ο(f(n)) : f(n)의 최고차식 이하의 모든 식들을 포함하는 집합
- Ω(f(n)) : f(n)의 최고차식 이상의 모든 식들을 포함하는 집합
- θ(f(n)) : 계수를 무시하고, 최고항이 정확하게 f(n)이 되는 함수들의 집합
~cpp
θ(f(x)) = Ο(f(x)) ∩Ω(f(x))
ex)
1. g(n) ∈ Ο(f(n)) ⇔ f(n) ∈ Ω(g(n))
- g(n)은 f(n) 이하이다.
2. g(n) ∈ θ(f(n)) ⇔ f(n) ∈ θ(f(n))
- g(n)과 f(n)의 최고차는 같다.
3. a,b > 1 에 대해서
log n ∈ θ(log n)
a b
∵ log n = log n / log a = 1/log a * log n
a b b b b
- log 함수는 base에 관계없이 같은 차수이다.
4. b > a > 0
- a^n ∈ Ο(b^n)
- a^n not∈ θ(b^n)
5. a^n ? n!
- a^n ∈ Ο(n!)
- a^n not∈ θ(n!)
cf. log n < n < n*log n < n^2 < ... < n^100 < 2^n < 3^n < n!
김성권 교수님 - 알고리즘 노트에서 정리 --이선우
- 위에서 다음으로 생각이 바뀌었습니다. 반복횟수를 넣는다기 보다는... ~에 비례한다라는 식으로.. 예를 들어 반복횟수가 n+3 이런식이라도 O(n)이렇게 되는 것이져..맞을까?--;
- 이것을 이해하기 위한 소스
~cpp
// x의 n승을 구하는 함수.
double lalala(double x, int n)
{
double y=1.0;
while(n--) y *= x;
return y;
}
- 이 함수의 수행시간을 구하면 O(n)이 된다. 왜냐? 이 함수의 수행시간을 좌우하는 부분은 while문일것이다. while문에서 n번 도니까 O(n)이 되는 것...(맞나?--;) 그런데! 이 함수보다 생긴건 복잡하지만 효율이 좋은 함수를 만들수 있다.
~cpp
// x의 n승을 구하는 또다른 함수
double lalala2(double x, int n)
{
double temp=1.0;
if(n == 0) return 1.0;
if(n == 1) return x;
if(n%2) /* n이 홀수이면 */ // 재귀 호출을 썼습니다.
{
temp = lalala2(x, n/2);
return temp*temp*x;
}
else /* n이 짝수이면 */
{
temp = lalala2(x, n/2);
return temp*temp;
}
}
- 이 함수의 수행시간을 구하면 O(log2n)이 된다! 고등학교 때 배운 바에 의하면 n>log2n 이라는 전설이..--;(log뒤의 숫자 2는 밑입니다.)
- 이 소스들을 예로 든 이유는 같은 기능을 하는 함수라도 효율성을 따져 가면서 만들면 좋다는..
; 겁니다..;
- O(log2n)이게 왜 이렇게 되는지 모르는 사람을 위해.. 귀납법을 쓰도록 하겠습니다.
~cpp
여기서 x^2n=(x^n)^2, x^(2n+1)=(x^n)^2 * x 이렇게 쓸수 있겠죠?
n=1 : f(1)=0
n=2 : f(2)=1
n=4 : f(4)=f(2)+1=2
n=8 : f(8)=f(4)+1=3
...
n=2^k : f(2^k)=k
그러므로 log2k 가 되는 것입니다.
