[알고리즘] 알고리즘의 기초 정리자료-2

알고리즘 기초 정리자료-1 (분할정복, 동적 프로그래밍, 욕심쟁이)에 이어서 만들었기 때문에,

링크는 여기에 → https://sohyunsaurus.tistory.com/6

 

(4) 정렬 알고리즘 

❋ 내부정렬 ↔️ 외부정렬

정렬하고 싶은 모든 데이터를 주기억장치에 적재시킨이후에 하는 것을 내부정렬이다.

• 정렬하는 방식에 따라 내부 정렬은 비교 기반 알고리즘 ↔️ 데이터 분포 기반 알고리즘으로 나눠진다.

❋ 안정적 정렬

동일한 값을 갖는 데이터가 정렬 전의 상대적 위치와 정렬 후의 상대적 위치가 동일할 경우

 

❋ 제자리 정렬 

내가 정렬하고 싶은 입력 데이터를 저장하는 공간 이외에 추가적인 공간이 상수개 만큼 필요할 때는 제자리 정렬

추가적으로 필요할 때엔 제자리 정렬이 아니다. 

 

정렬 방식	알고리즘	성능	안정적	제자리	특징
비교 기반	버블 정렬	O(n^2)	O	O	최악 O(n^2) 최선 O(n)
	선택 정렬	O(n^2)	X	O	언제나 동일
	삽입 정렬	O(n^2)	O	O	최악 O(n^2) 최선 O(n)
	셸 정렬	O(n^2)	X	O	삽입 정렬의 단점을 보완
	합병 정렬	O(nlogn)	O	X	분할정복 방법 적용, 점화식
	퀵 정렬	O(nlogn) O(n^2)	X	O	분할정복 방법 적용, 점화식
	힙 정렬	O(nlogn)	X	O	힙 자료구조 장점 활용. 초기힙 구축, 최댓값 삭제 및 힙 재구성의 과정
데이터 분포 기반	계수 정렬	O(n)	O	X	입력값의 범위가 입력 크기 n보다 작거나 비례하는 경우
	기수 정렬	O(n)	O	X	입력 원소의 값의 자릿수가 상수인 경우

 

 (5) 탐색 알고리즘

탐색 방법	탐색 시간	특징
순차 탐색	O(n)	비정렬 데이터 탐색에 적합 → 모든 리스트에 적용 가능 삽입 O(1) 탐색과 삭제 O(n) → 데이터가 큰 경우에는 부적합
이진 탐색	O(logn)	정렬된 입력 배열에 대해서만 적용 가능 삽입/삭제가 빈번한 경우 정렬 상태 유지를 위해 O(n)의 자료 이동이 필요 → 부적합
이진 탐색 트리	O(logn) O(n)	이진 탐색 트리의 정의 연산(탐색, 삽입, 삭제 → 자식 노드의 개수에 따라 구분하여 처리 최악의 경우 → 리프 노드를 제외한 모든 노드의 차수 1인 경우 → 경사 이진 트리
흑적 트리	균형탐색트리 O(logn)	이진 탐색 트리 + 균형 탐색 트리 4가지 성질 탐색 → 이진 탐색 트리의 탐색과 동일 삽입 → O(logn) → 적색 노드가 연다아 나타나는 것을 방지하기 위해 노드의 구조 및 색깔을 변결
B-트리		5가지 성질 탐색 → 이진 탐색 트리의 탐색과 유사 삽입 → (2t-1)개의 키를 갖는 노드를 만나면 노드 분할
해싱	해시 함수: 제산 잔여법, 비닝, 중간 제곱법, 문자열을 위한 함수 충돌해결방법 : 개발 해싱(연쇄볍), 폐쇄 해싱(개방 주소법→종류: 버킷 해싱, 선형 탐사(1차 클러스터링 문제) 이차 탐사(2차 클러스터링 문제, 이중해싱)