[[TableOfContents]]

= 기본 개념 =
 * 처음인 주제에 열라 어렵다--; 갠적으로 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 가 되는 것입니다.
}}}

 * 이건 또 얼마전에 본 글인데.. 재귀호출은 가급적 쓰지 말라 하더군요. 저 자신도 엄청 싫어합니다. 
  * 기본적으로 함수를 호출하는 것 자체가 하나의 Overhead이며, 재귀호출의 경우 계속 함수스택에 해당 함수코드부분이 쌓여나가는 것이므로, n 의 값이 커질 경우 메모리를 많이 이용하게 됩니다. 하지만, 재귀호출의 표현법은 일반 수열의 표현식을 거의 그대로 이용할 수 있습니다. 코드가 간단해집니다.

== 파스칼의 삼각형 ==
["PascalTriangle"]

----                                                      
["DataStructure"]