수업 내용 정리/Data Structure (3) 썸네일형 리스트형 10. Sorting and Searching Algorithms Selection Sort 1. 일단 전체에서 가장 작은 값 찾아서 앞으로 가져옴=> 첫번째는 sorted 나머지는 unsorted(최솟값이랑 현 위치만 바꾸고 나머지는 순서 바뀌지 않음) 2. unsorted에서 가장 작은 값 찾아서 또 땡겨옴 => 두번째까지 sorted 나머지 unsorted 3. 위 과정 반복 시간복잡도: 갯수가 n개일때 비교횟수는 n*(n-1)/2이므로 O(n**2)이다. template int MinIndex(ItemType values[], int startIndex, int endIndex) // Post: Returns the index of the smallest value in // values[startIndex]..values[endIndex]. { int inde.. 9. Priority Queues, Heaps, and Graphs Heap complete binary tree & 조상>자식 ReheapDown 노드가 heap의 규칙을 어기고 있을 때 하는 것 노드의 자식노드 중 자기보다 크고 둘중에 큰것을 고른다음 바꾼다. 이과정을 반복해서 자기 자리를 찾는다. ReheapUp 조상노드가 자기보다 작다면 올라가는 것 Removing the largest element 1. bottom rightmost element를 root로 가져옴 2. bottom rightmost element를 삭제 3. root를 ReheapDown 해줌 Inserting new element 1. bottom leftmost place에 삽입 2. ReheapUp 해줌 Priority Queue only the highest-priority eleme.. 8. Binary Search Trees binary tree이다. 뭐 ancestor, descendant 다양한 용어가 있지만 쉬우니 넘어가자 높이가 H인 full tree는 2**h - 1개의 노드를 갖는다. N개 노드를 가질때 최대/최소 높이: 최대 높이는 일렬로 노드가 늘어설 때 이므로 N이고 최소 높이는 full tree일때 이므로 log(N+1)이다. linked list 와 binary tree, 서치 시간복잡도 비교 둘다 최악의 경우 O(N)으로 똑같음 ㄷ 색다른 binary tree: 오른쪽 루트노드는 중간보다 크고 왼쪽은 작음, 서치 시간 복잡도 O(logN)으로 링크드 리스트보다 효율적임 CountNodes(recursive) 졸라 간단하다. 복잡하게 생각할 수 도있으나 이렇게 간단하게 짤 수 있으니 알아둘 것. Retri.. 이전 1 다음
