- 라 렵다
; 갠로 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 가 되는 것다.
