1. 정렬
1-1. 최악
① 5, 7, 9, 10, 15, 3 내가 찾고싶은 데이터는 10. 10을 찾으려면 (첫 시작점인) 5부터 시작해서 4번째 칸에서 10을 찾는다. 근데 그 뒤에 또 10이 있을 가능성이 있으니... 결국 끝까지 풀스캔해서 찾아야만 한다. 최악!
1-2. 프라이머리 키
② 5, 7, 9, 10, 15, 3 [프라이머리 특성]일때. 데이터를 스캔하다가 10을 찾으면 거기서 바로 멈춘다! 뒤에까지 찾으러 가지 않는다. 그래서 데이터에선 primary가 중요하다!
1-3. 정렬의 목적
③ 3, 5, 7, 9, 10, 15 [sort] 정렬이되면 퍼포먼스가 무조건 좋아진다. (6)/2 = 3이니 데이터를 스캔할 때, 첫번째로 3번째 자리에 있는 9에 액세스를 한다. 9 앞에 10이 있을 수는 없으니까(순차 정렬이 된 상태니까) 앞의 데이터는 과감하게 버려버림. 바로 9 이후에 있는 데이터를 찾는다. 또한, 10이랑 동일한걸 찾으면 멈춘다.
선형적 - 비례해서 올라가는 것.
만약, 배열의 크기에 따라 배열의 모든 원소를 확인해야 한다면 그 알고리즘은 선형적이다. 배열의 크기가 두 배로 늘어나면 알고리즘의 실행 시간도 대략 두 배로 늘어난다.
log방식 - 주로 ‘이진트리 검색 (반씩 나눠가며 찾는 것)’이라는 단어와 함께 사용된다.
성능이 더 뛰어나며 많은 알고리즘이 이러한 형태로 설계되어 있다.
(엄청 천천히 증가한다. 값이 너무 크니까 로그 방식으로 사용하면 값을 작게 표현할 수 있음. = 입력 크기가 2배로 증가할 때마다 실행 시간이 고정된 비율로 늘어남. 2배 증가하면 시간도 2배로 늘어나는 선형적과는 다름)
2. 정렬의 장점
[ 2, 3, 3, 4, 5, 9, 10 ] - 데이터에 3이라는 중복값이 존재하는 경우 1. 클러스터링이 된다. 정렬된 상태로 찾으면 동일한게 나오지 않는 순간 멈출 수 있다. ex) 3이 중복으로 있을 수 있으니까 계속 가다가, 4가 나오는 순간 바로 멈추는 것. 2. 이진트리 검색(바이너리 서치)이 된다. 정렬이 되어있으니 중간을 잡아서, 위만 보든, 밑에만 보든 계속 반을 버릴 수 있다. 정렬이 되어있으면 데이터를 버릴 수 있어서 속도가 위의 표와 같이 증가
클러스터링(Clustering)
비슷한 특성을 가진 데이터들을 묶어 같은 그룹(클러스터)으로 만드는 기계 학습 및 데이터 분석 기법. 데이터 간의 유사성을 측정하고, 이 유사성을 기반으로 데이터를 그룹화
바이너리 서치(Binary Search)
정렬된 배열에서 특정한 값을 찾는 알고리즘. 이 알고리즘은 배열의 중간 값을 선택하고 찾고자 하는 값과 비교하여 값을 찾는 범위를 반으로 줄여가는 방식으로 동작
Share article