:)

Chapter 7.1-7.7Time ComplexityInsertion SortSelection SortMerge SortQuick SortHeap Sort예제 14 풀이합병정렬 알고리즘에서 레코드의 저장 횟수를 기준으로 할 때 시간복잡도는 대략 T(n) = 2n log n이 됨을 증명하기알고리즘 2.2문제) n개의 원소를 비내림차순으로 정렬입력) 양의 정수 n, 배열 S (인덱스는 1부터 n까지)출력) 원소를 비내림차순으로 정렬한 배열 Svoid mergesort ( int n, keytype S[] ) { if ( n > 1 ) { const int h = └n/2┘, m = n - h; keytype U[1...h], V[1...m]; copy S[1] through..

linear median finding algorithm시간복잡도가 Θ(n)임을 보여주기n T(n) ≤ c T(n) = Θ(n)hashing function에서 계수 a가 0이 아니어야 하는 이유계수 a가 0일 경우 데이터의 key값이 없어지기 때문에 0이 아니어야 한다.예제 8.1 풀이만약 n개의 키가 m개의 바구니에 균일하게 분포되어 있고, 각 키가 검색 키가 될 확률이 거의 같다고 하면, 성공한 검색의 평균 비교 횟수는 다음과 같다.n/2m + 1/2만약 키가 균일하게 분포되어 있고 n=2m이라면, 실패한 검색은 각각 2m/m = 2번의 비교만 필요하고, 성공한 검색은 평균 비교 횟수가 다음과 같다.2m/2m + 1/2 = 3/2만약 모두 같은 바구니에 분포되어 있을 경우 순차검색과 유사하나 같은..

1. n개의 노드에서 트리의 가장 작은 높이가 Ω(log n) = - 1 + log(n+1)임을 증명하기트리의 기본적인 특징: n개의 노드를 가진 트리는 n-1개의 간선을 갖는다.: 높이가 h인 이진트리가 가질 수 있는 최대 노드 개수는 2^(h+1)-1모든 레벨에 노드가 완전히 차있게 하여 높이를 가장 작게 만들기 위해서는 가장 많은 노드 개수를 가져야 한다.n n + 1 log(n+1) -1 + log(n+1) -> Ω(log n) = - 1 + log(n+1)2. direct access arrays의 공간을 축소할 때 linked list 자료구조를 사용할 수 있습니다. linked list를 사용할 경우 발생할 문제를 시간 복잡성과 함께 설명하기array와 linked list 비교locatio..

개념 요약Sorting algorithm: 배열의 요소를 특정 순서로 정렬하는 알고리즘1) Permutation sort (순열 정렬): 정렬된 입력을 찾을 때까지 순열을 생성한다.2) Selection sort (선택 정렬): 정렬되지 않은 배열에서 가장 작은 요소를 선택하고 해당 요소를 정렬되지 않은 배열의 시작에 배치한다.3) Insertion sort (삽입 정렬): 배열에서 정렬되지 않은 부분의 값이 선택되어 정렬된 부분의 올바른 위치에 배치된다.4) Merge sort (합병 정렬): 배열을 반으로 분할하여 각각 따로 정렬한 뒤 합병하여 정렬한다.ch.1 34번 문제풀이문제 : 아래 중첩 루프의 시간 복잡도 T(n) 구하기(어떤 양의 정수 k에 대해서 n이 2의 거듭제곱이라고 가정)i = n;..

생일 문제(Birthday Problem): 임의로 모인 사람들 중 생일이 같은 두 명이 존재할 확률을 구하는 문제Algorithms - Birthday Data.csv: 학생들의 이름, 서로 식별 가능한 ID, 생일 날짜 저장사용 언어 : Python생일이 같은 두 사람을 수동으로 결정하기 위해 pseudo code 작성bd_problem 함수를 만듦def bd_problem(총 모인 사람의 인원수): n_p 변수 정의 for문 시작 for i in range(n_p, 365): p 변수 정의 n_p와 p간의 관계 최종적인 확률을 probability 변수에 저장 임의로 모인 사람들의 총 인원수와 그 중 2명 이상의 생일이 겹칠 확률..