분류 전체보기5 알고리즘 005 1. Solve the exercise problem 14 of the chapter 7. # 합병정렬 알고리즘에서 레코드의 저장 횟수를 기준으로 할 때 시간복잡도는 대략 T(n) = 2nlgn 이 됨을 증명하시오. # 합병정렬(mergesort)은 분할 정복(divide and conquer) 알고리즘으로, 주어진 배열을 두 개의 작은 배열로 재귀적으로 분할한 후, 두 개의 작은 배열을 정렬하고 병합하는 과정을 반복하여 전체 배열을 정렬하는 알고리즘이다. 이 알고리즘에서 레코드의 저장 횟수는 다음과 같다. 1. 분할: 배열을 반으로 나누어 두 개의 작은 배열로 분할한다. 이때 각 레코드는 한 번만 복사되므로, 전체 레코드의 저장 횟수는 n이다. 2. 정렬: 두 개의 작은 배열을 재귀적으로 정렬한다. 이.. 2023. 4. 10. 알고리즘 004 1. Describe linear median finding algorithm. Show that its time complexity is Θ(n). 선형 중앙값 찾기 알고리즘은 n개의 원소로 구성된 배열에서 중앙값을 찾는 알고리즘입니다. 이 알고리즘은 다음과 같은 단계를 따릅니다. 1) 배열을 정렬한다. 2) 중앙값을 찾는다. import heapq lowar=[] highar=[] median=0 def MaxHeap(a): heapq.heappush(lowar,-1*a) def gMaxHeap(): a=heapq.heappop(lowar) return -1*a 이 알고리즘의 시간 복잡도는 배열을 정렬하는 데 O(n log n)의 시간이 소요되고, 중앙값을 찾는 데 O(1)의 시간이 걸리기 때문입니다.. 2023. 3. 29. 알고리즘 003 1. Prove that the smallest height for any tree on n nodes is Ω(lg n) = - 1 + lg(n+1). 트리의 높이가 h일 때, 최소 노드 개수는 다음과 같다. 높이가 0일 때, 노드 개수는 1개이다. 높이가 1일 때, 노드 개수는 2개이다. 높이가 2일 때, 노드 개수는 4개이다. 높이가 3일 때, 노드 개수는 8개이다. 이를 정리하면 높이가 h일 때, 최소 노드 개수는 2*h 라는 식을 얻을 수 있다. 반면, 최대 노드 개수는 이와 같은 방법으로 정리하면 2*(h+1)-1 로 정리할 수 있다. n개의 노드를 가진 트리의 높이를 h라 가정하면 최소노드 개수는 2*h 이고, 최대 노드 개수는 2*(h+1)-1 이므로 2*h 2023. 3. 18. 알고리즘 002 1. 문제설명 아래 중첩루프(nested loop)의 시간복잡도 T(n)은? 모든 경우를 다 고려하면 너무 복잡해지므로, n이 2의 거듭제곱이라고 가정해도 좋다. 즉 어떤 양의 정수 k에 대해서, n=2**k이다. i=n; while (i>=1){ j=i; while(j순환 호줄 사용 6월 생일인 사람을 피벗으로 정해 퀵 정렬을 사용한다. 2023. 3. 13. 이전 1 2 다음
