[C언어 알고리즘] 2.4.1 선택 정렬 알고리즘 성능 분석 [C언어 알고리즘] 2.4.1 선택 정렬 알고리즘 성능 분석 선택 정렬 알고리즘 성능을 분석합시다. 선택 정렬(base:컬렉션,n:원소 개수,compare:비교 논리) 반복(i:=n; i>1 ; i:= i-1) 반복(max=0,j:=1; j 언어 자료구조 알고리즘/디딤돌 알고리즘 (C언어) 2016.11.29
5.1 퀵 정렬 알고리즘 성능 분석 5.1 퀵 정렬 알고리즘 성능 분석 퀵 정렬 알고리즘 성능을 분석합시다. n 개의 원소인 배열을 정렬할 때 걸리는 수행 시간을 T(n)이라고 합시다. 퀵 정렬은 재귀적인 방법으로 해결하고 반 씩 나누어 재귀 호출이 이루어지는데 재귀 호출이 진행하기 전에 비교에 걸리는 시간을 S(n)이라고 합시다. 그리고 n 개인 원소를 재귀 호출 전에 비교하는 횟수는 n번이므로 S(n)=n입니다. T(n) = 2*T(n/2) + n = n^2T(n/n^2) + 2*n = ... = h*n 재귀는 원소 개수가 1보다 작으면 탈출하므로 n^h =1 일 때 더 이상 재귀 호출은 발생하지 않습니다. h = logn이므로 T(n) = nlogn 그런데 이처럼 퀵 정렬에서 재귀 호출 시에 절반으로 나누어지는 것은 피벗을 잘 선택하.. 언어 자료구조 알고리즘/디딤돌 정렬 알고리즘 (C언어) 2016.11.25
4.1 삽입 정렬 알고리즘 성능 분석 4.1 삽입 정렬 알고리즘 성능 분석 삽입 정렬 알고리즘 성능을 분석합시다. n 개의 원소인 배열을 정렬할 때 비교에 걸리는 수행 시간을 T'(n)이라고 합시다. 삽입 정렬의 내부 반복문에서 비교에 걸리는 시간을 S(n)이라고 하면 S(n) = n-1입니다. T'(n)은 다음과 같습니다. T'(n) = S(2) + S(3) + ... + S(n) = 1 + 2 + 3 + ... +(n-1) 따라서 삽입 정렬의 비교에 걸리는 시간은 O(n^2)이라고 말할 수 있습니다.그리고 삽입 정렬에서 교환과 비교 횟수는 같습니다. 따라서 선택 정렬 알고리즘을 수행 시간은 O(n^2)이라고 말할 수 있습니다. 언어 자료구조 알고리즘/디딤돌 정렬 알고리즘 (C언어) 2016.11.25
3.1 선택 정렬 알고리즘 성능 분석 3.1 선택 정렬 알고리즘 성능 분석 선택 정렬 알고리즘 성능을 분석합시다. 선택 정렬(base:컬렉션,n:원소 개수,compare:비교 논리) 반복(i:=n; i>1 ; i:= i-1) 반복(max=0,j:=1; j 언어 자료구조 알고리즘/디딤돌 정렬 알고리즘 (C언어) 2016.11.24