[이산수학] Chapter 4. Algorithms

1. Introduction

 - 알고리즘은 다음과 같은 특징들을 가지고 있다.

 1) input

 2) output

 3) precision : 정확하게 서술되어야 한다

 4) determinism :  수행의결과는 unique하다. 또한 input과 선행된 step에 따라 결정된다.

 5) finiteness : 알고리즘은 끝나야 한다. (유한개의 instruction이 수행된 이후엔 멈춰야 함)

 6) correctness : 알고리즘에 의해 도출된 output은 맞아야 한다.

 7) generality : 모든 input에 대해 적용되어야 한다. 

 

2. Examples of Algorithms

 - 큰 수 찾기 알고리즘, 문자열 찾기 알고리즘, 삽입 정렬 알고리즘

 - Randomized Algorithms (무작위 알고리즘) : 난수를 발생시켜 진행과정을 결정하는 알고리즘

  

3. Analysis of Algorithms

  - Useless program : 너무 오랜 시간이 걸리거나 너무 많은 space를 차지해서는 안됨. 

  - Complexity of algorithms : 실제로 이 알고리즘이 수행되는데 걸리는 시간은 정확히 구하기 힘들다. 따라서 우리는 직접 시간을 재는 것 보다는 알고리즘의 시간을 estimate, 추정할 것이다! 이 때, 알고리즘이 수행되는데 필요한 time 혹은 space를 바로 알고리즘의 Complexity라고 한다.

  (프로그램이 돌아가는 컴퓨터, data가 표현되는 방식, 프로그램이 기계언어로 어떻게 번역되었는지, 무슨 언어가 쓰였는지 등이 Performance에 영향을 미치는 parameter들이다)

 

  1) Time complexity

    - Best-case time 

    - Worst-case time

    - Average-case time

 

    - f(n) = O(g(n)) : g(n)은 f(n)의 상한선, asymptotic upper bound for f (f의 상한점근선)

      |f(n)| <= C1|g(n)|  (C1은 양의 상수)

 

     ex) 60n^2 + 5n + 1 <= 60n^2 + 5n^2 + 1n^2 = 66n^2

         즉, C1 = 66 -> 60n^2 + 5n + 1 = O(n^2)

 

          2n + 3logn <= 2n + 3n = 5n

          C1 = 5 -> 2n + 3logn = O(n)

 

 - f(n) = Ω(g(n)) : g(n)은 f(n)의 하한선, asymptotic lower bound for f (f의 하한 점근선)

       |f(n)| >= C2|g(n)|  (C1은 양의 상수)

 

   ex) 60n^2 + 5n + 1 >= 60n^2

         즉, C2 = 60 -> 60n^2 + 5n + 1 = Ω(n^2)

 

          2n + 3logn <= 2n 

          C2 = 2-> 2n + 3logn = Ω(n)

 

 

 - f(n) = Θ(g(n)) : g(n)은 f(n)과 가장 가까운 점근선, asymptotic tight bound for f

 

     ex) 60n^2 + 5n + 1 = O(n^2) 이고 60n^2 + 5n + 1 = Ω(n^2) 이니까 

         60n^2 + 5n + 1 = Θ(n^2)

 

        2n + 3logn = O(n) 이고 2n + 3logn = Ω(n) 이니까 

        2n + 3logn = Θ(n)

 

요거는 기본이니까~

 

 

4. Recursive Algorithms : 재귀적 알고리즘, 자기 자신을 호출하는 알고리즘

 ex ) n! = n(n-1)! = n(n-1)(n-2)! ... 

      fibonacci sequence : f1 = 1, f2 = 2, fn = fn-1 + fn-2 for n>= 3