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.0095 sec