01. 알고리즘 분석

자료구조랑 겹치는 부분이 있다. 작년에 강유 교수님 자료구조 들었을 때도 비슷한 내용을 처음에 배워서 그 부분을 참고할 것이다. 그리고 이번에는 다른 책들을 참고하지 않는다. 알고리즘 분석 방법은 어차피 앞으로 계속 연습할 내용들이기 때문에, 굳이 책을 참고하고 예제를 만들지 않아도 된다고 생각했다.

 

 

• 좋은 알고리즘이란?

1. Be Clear
   : 알아듣기 쉽고, 간단하고, 명료하게 쓰여져야 한다.
   (+ mathematical notation을 남발하면 clarity가 떨어진다.)

2. Be Efficient $\Rightarrow$ 초점
   : 같은 문제를 해결하는 알고리즘이라면 최대한 적은 자원을 사용하는 것을 택해야 한다. 이 때 자원이란 주로 시간과 공간을 의미하므로 시간복잡도, 공간복잡도를 최소화하는 것이 알고리즘 효율성을 높이는 데에 중요하다.
   : 특히 시간복잡도의 경우 input크기에 의존적임에 주의한다.

---

• Asymptotic notation(점근 표기법)

  곧 할게

---

• 알고리즘 분석

1. Correctness

   • Loop가 없는 알고리즘의 경우 case를 나눠 가며 증명한다.

   • Loop가 있는 알고리즘의 경우 Loop Invariant를 찾는다.

     • Loop Invariant : Loop가 반복되어도 변하지 않는 성질

     • Loop가 여러 개 있는 알고리즘의 경우 가장 outer loop를 기준으로 invariant를 설정한다.

       : recursive algorithm도 전체 알고리즘의 수행 구조가 loop와 비슷하다. 따라서 recursive algorithm을 증명할 때에도 마찬가지로 Loop Invariant를 찾는다. 이 때는 recursive call을 가장 outer loop라고 간주하고, recursive call이 반복되어도 변하지 않는 성질을 찾으면 된다.

   (예)

   //Insertion Sort
   for j=2 to n
      key = A[j]
    //insert A[j] into sorted A[1~j-1]
    i = j-1
    while i>0 and A[i] > key
        A[i+1] = A[i]
        i = i-1
    A[i+1] = key

    

   1. Loop Invariant 설정

      "A[1 ... j-1]이 정렬되어 있음"

   1. Step 1 Initially

      j=2일때 해당 Loop invariant는 성립한다.

   2. Step 2 Maintain

      iteration이 시작할 때 Loop invariant가 성립한다는 것을 가정하면 그 다음 iteration에서도 앞서 설정한 Loop invariant가 성립한다는 것을 보인다.(수학적 귀납법과 유사하다)

   3. Step 3 Terminate

      이 알고리즘의 Loop는 반드시 종료되는데, 종료 시점에서도 Loop invariant가 유지되므로 해당 알고리즘이 올바른 결과를 산출한다는 것을 증명할 수 있다.

       

      : 이 알고리즘의 종료 시점에 j는 n+1이다. 그리고 step 1과 step 2에 의해 종료 시점에도 Loop invariant가 유지될 것이다. 따라서 Loop invariant에 j=n+1를 대입하면 종료 시점에 A[1 ... n]이 정렬되어 있다는 것을 알 수 있다.

2. Efficiency(complexity)

   • resources

     (1) time $\longrightarrow$ 주로 시간복잡도가 공간복잡도보다 분석하기 더 어렵다.

     (2) memory, communication cost