U E D R , A S I H C RSS

Data Structure/Foundation



1. 기본 개념

  • 처음인 주제에 열라 어렵다; 갠적으로 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 의 값이 커질 경우 메모리를 많이 이용하게 됩니다. 하지만, 재귀호출의 표현법은 일반 수열의 표현식을 거의 그대로 이용할 수 있습니다. 코드가 간단해집니다.

1.1. 파스칼의 삼각형

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:05
Processing time 0.0199 sec