선택, 삼항 비교기를 사용하여 가장 큰 집합 찾기

Question

S를 n> 0의 고유 정수 집합이라고 가정합니다. n은 3의 거듭 제곱이라고 가정합니다. 삼원 비교는 집합 S의 세 숫자를 비교하여 가장 작은 것으로부터 가장 작은 것까지.

가능한 가장 적은 수의 3 진 비교를 사용하여 집합 S에서 가장 큰 수를 찾는 효율적인 알고리즘을 설명하십시오. 왜 알고리즘이 올바른지 설명하고 최악의 경우에 사용하는 정확한 3 항 비교 수를 진술하십시오.

이것은 중간 질문이었습니다. 다음

내 대답했다 :

T (N) = 3T를 (N/3) + 1

가 해결 (N/2) -1

더 효율적인 방법이 있는가 이것을하기 위해 ?

감사합니다.

Answer 1

나는 그 이상을 할 수 있다고 생각하지 않습니다. 각 비교를 통해 고려에서 두 개의 숫자를 정확히 폐기 할 수 있습니다. 당신은 (n-1)/2가 아니라 (n/2) -1이되어야합니다.