검색어 입력폼

Foundations of Algorithms using C++ pseudocode 7장 연습문제

저작시기 2016.06 |등록일 2017.03.26 한글파일한컴오피스 (hwp) | 6페이지 | 가격 2,000원

소개글

Foundations of Algorithms using C++ pseudocode 7장 연습문제입니다

목차

없음

본문내용

7장 연습문제

#3

삽입정렬에서 최악인 경우 내림차순으로 정렬되있을때 매번 삽입이 가장 앞에 되기 때문에 레코드지정 횟수가 최악이다.

정렬된 배열이 하나씩 추가되는 정렬방법이기 때문에 새로운 원소가 맨앞에 추가될때마다 정렬된 배열이 한칸씩 뒤로 밀리므로 I=2일 때 2번 I=3일 때 3번 하다보면 I=n일 때 n번 뒤로 밀게 된다.

그러므로 2+3+…n까지의 합인 n(n+1)/2 ? n^2/2가 된다.

W(n) = n^2/2

평균의 경우 최악의 경우에서 비해 평균적으로 중간쯤에 삽입된다고 하면 뒤로 밀게되는 배열의 개수가 반으로 줄어 n^/2*1/2 쯤 된다

A(n) = n^2/4

#9
순열 [n,n-1,…,2,1]의 역의 개수가 n(n-1)/2개 임을 보여라
(n,n-1),(n,n-2) ,(n,n-3),…,(n,3),(n,2),(n,1)//n-1개
(n-1,n-2),(n-1,n-3),(n-1,n-4),…,(n,3),(n,2),(n,1)//n-2개

참고 자료

없음
다운로드 맨위로