일반적으로 두 배열을 병합

Question

A1 = {10, 20, 30, 40, 50, 60}과 A2 = {15, 25, 35, 45}이 두 배열 인 경우 두 배열을 병합하는 데 필요한 비교 수는 얼마입니까?

이 문제를 solvng 내 의견이

A1 = {10, 15, 20, 30, 40, 50, 60}; A2 = {25, 35, 45}

25, 4 비교를 병합 할 것입니다 외모

처럼 그래서 지금,이 개 비교는 충분하다, 15 을 병합하는 것입니다 충분하다, 그래서 지금은 볼 것입니다

A1 = {10, 15, 20, 25, 30, 40, 50, 60}; A2 = {35, 45}

은 그래서 지금, 8 개 비교는 충분하다, (45)을 병합 그래서 지금, 6 개 비교가 충분하다 그것을 것 같이 보인다

A1 = {10, 15, 20, 25, 30, 35, 40, 50, 60}; A2 = {45}

을 35 병합에 의지 외모

A1 = {10, 15, 20, 25, 30, 35, 40, 45, 50, 60}

같은 따라서 012 비교 단위가 충분합니다. 하지만 그렇지 않습니다.

무엇이라고 말합니까?

Answer 1

이것은 두 줄의 사람과 비슷하며 은행 계좌입니다. 각 선의 앞에 2 명이있는 한, 그것을 비교하여 어느 것을 취해야하는지 결정해야합니다. 한 행이 비어있는 경우 비교하지 않고 다른 행의 나머지 모든 사용자를 첨부 할 수 있습니다. (이 비유는 입력이 링크 목록이라고 가정합니다. 배열을 병합하는 경우 다른 줄의 꼬리를 복사해야하고 대답은 다릅니다.)

이 모든 것을 염두에두고 보면보기가 어렵지 않습니다. 비교 횟수는 병합중인 값에 따라 다릅니다. 최소한 min (m, n)입니다. 여기서 m과 n은 입력 길이입니다. 최대 값은 m + n-1입니다.

Answer 2

두 배열을 병합하는 동안 요소를 그대로 유지하는 추가 배열을 사용합니다 정렬 및 병합.

경우에 따라 B 인 B.length = A1.length+A2.length의 세 번째 배열을 유지합니다.

배열의 병합 및 해당 숫자 비교는 다음과 같이 : - 따라서, 우리는

B.

의 나머지 요소를 복사

A1[0]<A2[0] --> B[0] = A1[0] 
A1[1]>A2[0] --> B[1] = A2[0] // total number of comparisons is 2 

A1[1]<A2[1] --> B[2] = A1[1] 
A1[2]>A2[1] --> B[3] = A2[1] // total number of comparisons is 4 

A1[2]<A2[2] --> B[4] = A1[2] 
A1[3]>A2[2] --> B[5] = A2[2] //total number of comparisons is 6 

A1[3]<A2[3] --> B[6] = A1[3] 
A1[4]>A2[3] --> B[7] = A2[3] //total number of comparisons is 8 

이 후, B에 남아있는 요소가없는

는

B = {} 10152025303540455060

따라서 비교의 수는 8과 아니다 - 다음과 같이 생성 된 어레이는 20