💡빠른정렬 - 기준점(pivot)을 기준으로 배열을 둘로 쪼갠다 - 기준점보다 작으면 왼쪽, 크면 오른쪽으로 분리 - 다시 왼쪽, 오른쪽 배열에서 기준점을 잡고 분리 - 배열에서 기준점을 제외하고 모든 원소와 비교하므로 점화식은 T(n) = n-1 그 외 정렬이나 합병 과정은 없음 - 일정 복잡도 계산 X quickwort(){} partition(){} ✔️ 최악의 시간복잡도 - 이미 오름차순으로 정렬되어 있어 왼쪽 배열은 아무것도 없고 오른쪽에는 정렬된 배열이 남아 무의미하게 계속 기준을 잡고 비교하는 과정을 거치기 때문 - T(n) = T(0) + T(n-1) + n -1 , if n>0 (* n개의 배열을 비교하면서 n-1 비교, 왼쪽은 0, 오른쪽은 다시 n-1개의 배열로 이뤄짐) = n(n-1..
분류 전체보기
💡합병 정렬(Mergesort) - n개의 정수를 가진 배열을 올림차순으로 정렬 - 배열의 원소의 개수가 1이 될때까지 반으로 분할하여 분리한 배열을 각각 따로 정렬한 후 취합 void mergesort(int n, int s[]){ // 배열을 쪼개는 함수 const int h = n/2, m = n-h; int U[1...h], V[1...m] // 배열의 인덱스를 표현(원소의 개수) if(n>1){ // U배열에 S배열의 1~h번째 원소를 복사 // V배열에 S배열의 h+1~n번째 원소를 복사 mergesort(h,U); mergesort(m,V); merge(h,m,U,V,S); } } void merge(int h, int m, const int U[], const int V[], const i..
💡 분할정복(Divide-and-Conquer) - 해결하기 쉽도록 문제를 여러개의 작은 부분으로 나누고 나눈 문제를 각각 해결하는 방식(하양식 방식, top-down) 💡 이진검색 - 찾고자 하는 원소 x 와 정렬된 배열에서 배열의 중간에 위치한 항목과 일치한지 비교 - 일치하지 않을 경우, x가 중앙보다 작으면 왼쪽, 크면 오른쪽 반쪽을 선택해 다시 해당 반쪽의 중앙을 선택 (반쪽 배열에서 재귀적으로 이분 검색) //이진검색 알고리즘 ✔ 최악의 경우 시간복잡도 분석 - n이 2의 제곱일 때와 아닐때로 나눌 수 있지만 자세한 설명은 생략하고 W(n) = ⌊logn⌋ +1 *n이 크면 1은 무시 - 귀납적 증명
💡알고리즘 이란? - 주어진 문제를 논리적으로 해결하는 과정 - 분석을 통해 효율성 파악, 효율성을 정량화 - 알고리즘은 프로그래밍 언어에 독립적 (언어에 따라 구현 문법은 좀 다르겠지만 원리는 동일하게 동작) ✔알고리즘의 따라 효율이 달라질 수 있다? 예1) 순차검색 vs 이진검색 - 순차검색은 처음부터 찾고자 하는 원소가 나올 때까지 진행 -> 원소가 가장 마지막에 있으면 시간 오래 걸림 - 이진검색은 중간에 있는 원소부터 시작해 찾고자 하는 원소보다 큰지 작은지에 따라 오,왼으로 이동해 다시 중간 원소와 비교 -> 비교적 시간 단축 예2) 피보나치항 계산의 재귀 vs 반복 - 반복문을 사용해 계산된 항의 개수는 n+1 - 재귀함수를 사용해 계산된 항의 개수는 2^(n/2) (단, n>=2) ex) ..
