본문 바로가기

알고리즘

 (5)
알고리즘 과제6 1. Read chapters 7.1 – 7.7. 2. Solve the exercise problem 14 of the chapter 7. 14. 합병정렬 알고리즘(알고리즘 2.2와 2.4)에서 레코드의 저장 횟수를 기준으로 할 때 시간복잡도는 대략 T(n) = 2n lg n이 됨을 증명하시오. 합병정렬을 하기 위해서는 1. 기존의 주어진 배열(S[])을 두개의 배열을 가운데 인덱스를 기준으로 나누는 과정이 필요하다. 2. 나누어진 배열을 각각 U[1...h]와 V[1...m]에 copy해 저장한다. 3. copy한 값을 각각 mergesort 한다. 4. mergesort한 배열들을 다시 S[]로 합친다. 레코드에 저장횟수를 기준으로 시간복잡도를 구한 것은 합병병렬의 평균의 시간 복잡도와 같다. 합병..
알고리즘 과제4 1. Describe linear median finding algorithm. Show that its time complexity is Θ(n). linear median finding은 Intelligent Quick Sort에 속한다. 이는 Quick Sort의 기준점(피벗)을 끝이 아닌 중앙에 두는 방식이다. 예시를 들어 설명을 해보면, [1,8,2,9,4,5,7]의 배열이 있다고 가정해보자. 1. 이의 피벗을 배열의 중앙에 있는 9로 잡는다. [1,8,2,9(피벗),4,5,7] 2. 피벗(기준점)을 기준으로 피벗보다 작은 값은 왼쪽에 피벗보다 큰 값은 오른쪽으로 정렬한다. 현재 배열에서 피벗인 9보다 큰 값이 없으므로 모두 피벗보다 왼쪽에 정렬이 되었다. [1,8,2,4,5,7,9(피벗)] 3..
알고리즘 과제3 1. Prove that the smallest height for any tree on n nodes is Ω(lgn) = -1 + lg(n+1) 트리의 노드가 n개이고, 깊이를 d라고 가정하자. 뿌리노드에는 노드가 1 개, 깊이가 1이면 최대 2개의 노드가 생성된다. 깊이가 2이면, 최대 2^2 = 4개의 노드가 생성된다. 그리고 깊이가 d이면 최대 2^d개의 노드가 생성된다. n < = 1 + 2 + 2^2 + ⋯ + 2^d 과 같은 부등식을 얻을 수 있다. 이는 수학적 귀납법에 의해 n < = 2^(d+1) -1로 나타낼 수 있다. 가장 작은 높이를 구해야하므로 위의 식을 풀면, n+1
알고리즘 과제2 1. Solve the problem 34 and 40 in chapter 1 1.34 아래 중첩루프의 시간복잡도 T(n) ? (어떤 양의 정수 k에 대해서, n = 2^k) i = n(2^k) 일때, j = i이므로 j =n(2^k) 이다. 따라서 두번째 while문은 한번 실행될 것이다. 그 후 i = i/2을 실행하여 i = 2^(k-1)이 된다. 다시 첫번째 while문으로 되돌아가 다시 실행이 되는데 이번에는 두번째 while문은 두 번 실행될 것이다. 이와 같은 과정을 첫번째 while문과 두번째 while문은 lgk번 반복될것이다. 따라서 Tout(lgk)*Tinner(lgk) = T(n) ==> lg²k 이다. 그러므로 T(n) = O(lg²n)이다. 1.40 f(n)과 g(n)은 점근적으..
알고리즘 과제 1 2. Manually determine the pairs of you who have the same birthday. Explain your method of solution. 1. 100명의 학생의 생일데이터를 다운로드합니다. 2. 다운받은 학생들의 생일 데이터를 오름차순으로 정렬합니다. 3. 오름차순으로 정렬한 생일 데이터를 사용하여 생일 같은 한 쌍의 학생이 있는지 확인합니다. 4. 01.19 , 01.20 , 02.07 , 03.09 , 03.28 , 04.28 , 05.18 , 06.16 , 07.19 , 08.02 , 09.05 , 09.25 , 10.19 , 11.15, 12.29 으로 총 15쌍의 학생들의 생일이 같다는 것을 확인할 수 있습니다. 4. Create code that cal..

티스토리툴바