[알고리즘] 자바를 이용해 비교, 분석한 삽입 정렬과 병합 정렬의 시간 복잡도(수행 시간)

소개

"[알고리즘] 자바를 이용해 비교, 분석한 삽입 정렬과 병합 정렬의 시간 복잡도(수행 시간)"에 대한 내용입니다.

목차

1. 오름차순으로 이미 정렬 되어있는 상태의 배열을 정렬
2.내림차순으로 정렬 되어있는 배열을 정렬
3. 크기가 작은 무작위로 정렬된 배열을 정렬
4.크기가 매우 큰 무작위로 정렬된 배열을 정렬
5.최종 결론

본문내용

사용한 정렬 알고리즘 :　삽입정렬, 병합정렬
정렬 순서 : 오름차순
사용 언어 :　자바
난수의 범위 :　0　∼　9９9

1. 오름차순으로 이미 정렬 되어있는 상태의 배열

a) 삽입정렬 -　이미 모두 정렬 되어있으니 삽입할 새 값이 이미 정렬 되어있다 친 인덱스의 값보다 작은지 비교하는 순환만 n번 해 실행시간은 최소 실행시간인 O(n)
b)　병합정렬 - 정렬할 배열의 원래 정렬 상태와 무관하게 배열을 두 번의 재귀호출을 통해 더 이상 나눌 수 없을 때까지 나눈 후, 각각의 쪼개진 것들을 비교 후 병합 하는걸 총 n번, 단 하나의 완성된 배열이 될 때 까지 log_2(n) 번 하니, n * log_2(n) 으로 실행시간은 O(n log n).
c) 결론 - 입력크기가 얼마나 크고 작든 배열이 이미 모두 오름차순으로 정렬 되어있는 경우엔 상수함수 수행시간을 가진 삽입정렬이 로그함수 수행시간을 가진 병합 정렬보다 빠름

<중 략>

참고자료

· 없음