Problem Set 6

1.      Read chapters 7.1 – 7.7.

     7.1 계산 복잡도

• 계산 복잡도 분석 = 문제의 분석만 의미 (알고리즘 포함X)
• 비교만으로 정렬하는 알고리즘 (sort only by comparisons of keys)
  ㄴ> 두 키를 비교하여 어떤 키가 큰지를 결정 가능. 키 저장은 가능하지만 키에 대한 다른 연산은 불가
• 키의 비교 횟수와 레코드의 저장(assignment) 횟수 기준으로 알고리즘 분석
• 입력 저장하는데 필요한 저장장소 이외에 + 알고리즘 수행하는데 얼마만큼 추가적인 저장장소 사용하는지
  • 추가 저장장소가 상수면? 제자리 정렬(in-place sort)
• 항상 비내림차순으로 정렬 (= 그게 오름차순 정렬 아닌지..? 아님! )
  • 정렬 알고리즘의 출력은 비 내림차순이다. 즉, 이전 원소는 다음 원소보다 작지 않다.
  • 오름차순이 아닌 이유는, 오름차순은 계속 수가 증가하는 개념 = 값이 같은 것을 포함하지 않음.
    때문에 비 내림차순이라고 표현
  • https://velog.io/@lky9303/On2-%EC%A0%95%EB%A0%AC-%EC%A0%95%EB%A6%AC

O(n^2) 정렬 정리

O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함.
O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.
O(n log n) : 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다. (선형로그형)
O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.

 

https://blog.chulgil.me/algorithm/

알고리즘의 시간 복잡도와 Big-O 쉽게 이해하기

 

     7.2 삽입정렬과 선택정렬

• 삽입정렬에서 키 비교 횟수 기준 최악/평균 시간복잡도 분석
• 삽입정렬에서 추가적인 저장장소 사용 분석 

     7.3 비교 한번에 기껏해야 역이 하나 제거되는 알고리즘의 하햔선

= 키의 비교 횟수 기준으로 2차시간 미안으로 알고리즘을 개선하는 것은 불가능 ! 

• 순열(permutation)에서 역(inversion)인 쌍(pair)은? 
  • i < j 이고 ki > kj인 (ki, kj) 
  • 순열에서 역이 없다 = 정렬된 순서의 순열이다 = 순열에서 역이 모두 제거되는 것이다. 
• 전치 순열(transpose)
  • 어떤 순열에서 pair는 그 순열이나 그의 전치 순열에서 역이지만, 둘 모두에서 역이 되지 않는다. ( *1/2)

     7.4 합병정렬(재고)

•  비교 한 번에 하나이상의 역 제거 가능
• W(n) = n lg n - (n-1)
• A(n) = n lg n - 1.26n
• T(n) = 2n lg n

 

• 합병정렬 알고리즘의 개선
  • 동적계획 방식 -> n lg n
  • 링크된 리스트 방식
  • 복잡한 합병 알고리즘 

     7.5 퀵정렬(재고)

     7.6 힙정렬 

            7.6.1 힙 구조와 기본적인 힙 연산 루틴

            7.6.2 힙정렬의 구현

     7.7 합병정렬, 퀵정렬, 힙정렬의 비교 

---

2.      Solve the exercise problem 14 of the chapter 7.

• 합병정렬 알고리즘에서(알고리즘 2.2, 2.4) 레코드 저장 횟수를 기준으로 할 때 시간복잡도는 대략 T(n) = 2 n lg n 이 됨을 증명하시오

합병 정렬(merge sort)은 분할 정복(divide and conquer) 방식을 이용하여 정렬을 수행하는 알고리즘입니다. 이 알고리즘은 입력 크기가 n인 경우, n개의 원소를 1개씩 나누어서 각각을 부분 리스트로 만든 다음, 부분 리스트를 두 개씩 합병(merge)하면서 정렬합니다.

-> 레코드 저장 횟수를 기준으로 시간복잡도를 계산하자면 ? 

각 단계에서 부분 리스트를 합병하는 데 필요한 레코드 저장 횟수 : 2n 

즉, 각 합병에서는 최대 2n개의 레코드가 저장됨. 

 

mergesort에서 분할된 배열 U, V를 새롭게 선언하여 사용함  첫 mergesort에서 입력 크기 n의 절반인 n/2 크기의 배열 두개가 생성 => n 크기의 저장장소가 새로 필요  다음 mergesort가 호출되면, (코드상에서는 U배열에 대한 mergesort가 수행된다)  n/4크기의 배열 두개가 생성 =>  n/2 크기의 저장장소가 필요 다음 재귀호출에서는 n/4 크기의 배열이 필요하다. 따라서 추가적인 저장장소의 크기는 다음과 같다.

https://somethoughts.tistory.com/21

정렬(2) - Θ(n lg n) 정렬 알고리즘: 합병정렬, 빠른정렬, 힙정렬

 

분할 단계에서는 입력 크기가 반으로 감소 ->  전체 합병 단계 수는 log n 

합병 정렬에서는 입력 크기가 n인 리스트를 먼저 반으로 나누고, 각각의 반으로 나눈 리스트들에 대해 다시 반으로 나누고, 그리고 다시 반으로 나누고, ... , 이렇게 리스트의 크기가 1이 될 때까지 반으로 나누는 과정 반복함 => 그러면 이제 각각의 리스트는 하나의 원소만을 가지고 있음 그리고 나서 각각의 리스트를 두 개씩 합쳐서 더 큰 리스트를 만듦.   이 과정에서 합쳐진 두 개의 리스트들은 이미 정렬된 상태이기 때문에, 이 두 개의 리스트를 합치는 과정에서는 새로운 정렬 작업이 필요 없음!!  그저 이 두 개의 정렬된 리스트를 합쳐서 더 큰 하나의 정렬된 리스트를 만들어내기만 하면 된다. => 이렇게 정렬된 리스트들을 합쳐나가면, 결국에는 하나의 정렬된 리스트가 만들어지게 됨.  이런 합병 정렬 알고리즘에서는 리스트를 계속해서 반으로 나누기 때문에,  리스트의 크기가 2^n이 되는 경우에는 리스트를 n번 나누어야 함 -> log n 도출됨 => 합병 정렬 알고리즘의 전체 합병 단계 수는 log n개 !

 

레코드 저장 횟수 = (전체 합병 단계 수) × (각 합병에서의 레코드 저장 횟수)
= log n × 2n

따라서, 합병 정렬 알고리즘의 시간복잡도 : O(nlogn)

이를 레코드 저장 횟수를 기준으로 나타내면 대략 T(n) = 2n log n 

---

3.    Refer to graph examples 1 and 2 on pages 21-22 of the class material titled 'Class material 06.pdf'. Given the graph, perform a Bi-Directional Search. The source vertex is 's', and the target vertex is 'D'. Draw the graphs for each step of your procedure.

 

4.      Can you improve this Bi-Directional Search algorithm? Describe the procedure. 

 

note. The third problem in the class material has been updated as described above.