Выбор, поиск самого большого набора с тройным компаратором

Question

Пусть S - множество из n> 0 различных целых чисел. Предположим, что n является степенью 3. Трехмерное сравнение может сравнивать три числа из множества S и упорядочить их из самый большой и самый маленький.

Опишите эффективный алгоритм, который использует как можно меньше тройных сравнений, чтобы найти наибольшее количество в наборе S.Explain, почему ваш алгоритм правильный и укажите точное количество тройных сравнений, которые он использует в худшем случае.

Вопрос был в середине срока.

Мой ответ был следующим:

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

решает (п/2) -1

Есть ли более эффективный способ сделать это ?

Спасибо.

Answer 1

Я не думаю, что вы можете сделать лучше, чем это. обратите внимание, что каждое сравнение позволяет отбросить ровно два числа из соображений. вы должны получить (n-1)/2, а не (n/2) -1.