Algorithm (3) 썸네일형 리스트형 해시 테이블 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조이다. 저장할 원소의 값으로, 저장할 위치를 계산할 수 있다. 평균 상수 시간에 삽입, 삭제, 검색이 가능하다. 매우 빠르게 자료를 저장/검색해야 하는 경우에 유용하다. 언제나 O(1) 검색 트리 이진트리 (BST) 각 노드는 하나씩의 키 값을 갖는다. 각 노드의 키 값은 다르다. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두 개의 자식을 갖는다. 임의의 노드의 키값은 자신의 왼쪽 자식 노드의 키 값보다 크고, 오른쪽 자식의 키값보다 작다. 최선 O(logn), 최악 O(n) 레드블랙트리 => O(logn) B-트리 => O(logn) 정렬 선택정렬 최소 값을 선택해서 이동한다 버블정렬 0 부터 i - 1 까지, 두 쌍의 값을 비교하여, 왼쪽 값이 크면 서로 위치를 바꾼다. 삽입정렬 a 배열의 0 에서 i-1 사이에서 value 보다 큰 값들을 뒤로 한 칸씩 이동하고, 그 값들 앞에 value를 넣는다 병합정렬 start, end의 중간 지점 계산하고 중간 지점을 기준으로 앞부분과 뒷부분을 정렬한 뒤에 병합한다. 시간복잡도는 O(nlogn). 공간복잡도는 병합할 배열과 동일한 크기의 임시 배열을 생성하기 때문에 O(n) 퀵정렬 임의의 값을 기준으로, 기준값보다 작은 값들은 배열의 앞부분으로 이동하고, 기준값보다 큰 값들은 배열의 뒷부분으로 이동하는 알고리즘. 시간복잡도는 평균 O(nlogn), 최악은 O(n^2) 공간복잡도는 O(1) 병합정.. 이전 1 다음