[리포트] 자료(資料)구조 관련 리포트입니다.
페이지 정보
작성일 19-05-25 21:42본문
Download : [레포트] 자료구조 관련 레포트입니다..docx
기타레포트 , 레포트 자료구조 관련 레포트입니다
제 목 : 여기에 題目을 쓰세요.
담당교수 :
과 목 명 :
학 과 :
학 번 :
이 름 :
제 출 일 :
◎ 주어진 문제 : k-way merge sort 에서 k=3보다 k=2를 더 많이 쓰는 이유는
♠ 고려해볼 것
시간적 비용( Timely Cost )
N 크기의 배열을 정렬하는데 필요한 시간 T( N ) 계산
2-Way
N 크기의 배열을 반으로 나눠 병합정렬하고, 정렬된 두 배열을 다시 N 번 비교해가며 최종적으로 정렬하는 방식임을 고려하여, 다음과 같은 수식을 이끌어낼 수 있다
T( N ) = T( ) + T( ) + 2( ) = 2T( ) + N
= 2{ 2T( ) + 2( ) } + N = T( ) + 2N
= { 2T( ) + 2( ) } + 2N = T( ) + 3N
= { 2T( ) + 2( ) } + ( k-1 )N
= T( ) + kN
= N 인 실수 k 가 존...
제 목 : 여기에 題目을 쓰세요.
담당교수 :
과 목 명 :
학 과 :
학 번 :
이 름 :
제 출 일 :
◎ 주어진 문제 : k-way merge sort 에서 k=3보다 k=2를 더 많이 쓰는 이유는
♠ 고려해볼 것
시간적 비용( Timely Cost )
N 크기의 배열을 정렬하는데 필요한 시간 T( N ) 계산
2-Way
N 크기의 배열을 반으로 나눠 병합정렬하고, 정렬된 두 배열을 다시 N 번 비교해가며 최종적으로 정렬하는 방식임을 고려하여, 다음과 같은 수식을 이끌어낼 수 있다
T( N ) = T( ) + T( ) + 2( ) = 2T( ) + N
= 2{ 2T( ) + 2( ) } + N = T( ) + 2N
= { 2T( ) + 2( ) } + 2N = T( ) + 3N
= { 2T( ) + 2( ) } + ( k-1 )N
= T( ) + kN
= N 인 실수 k 가 존재하므로, 이를 위 식에 대입해보면,
T( ) + kN = N T( 1 ) + kN
k = 이고 T( 1 ) 은 1 이므로,
N T( 1 ) + kN = N + N
총 N + N 만큼의 시간이 소요됨
3-way
M 크기의 배열을 3등분하여, 앞의 두 부분배열을 정렬한 후, 이 두 배열을 번 만큼 반복하며 정렬하고, 마지막 부분을 정렬한 뒤 다시 앞서 정렬된 부분배열과 M 번의 비교연산을 통하여 최종 정렬하는 과정을 거친다.
설명
[레포트] 자료구조 관련 레포트입니다.
T( M ) = T( ) + T( ) + + T( ) + M = 3T( ) +
= 3{ 3T( ) + } + = T( ) + 2( )
= { 3T( ) + } + 2( ) = T( ) + 3( )
= { 3T( ) + } + ( k-1 ) ( )
= T( ) + k( )
= M 인 실수 k 가 존재하므로, 이를 …(skip)
[리포트] 자료(資料)구조 관련 리포트입니다..docx( 63 )
레포트/기타
다.
순서
레포트,자료구조,관련,레포트입니다,기타,레포트
[리포트] 자료(資料)구조 관련 리포트입니다. , [레포트] 자료구조 관련 레포트입니다.
Download : [레포트] 자료구조 관련 레포트입니다.