Требуется минимальное количество сравнений

Question

Каково минимальное количество сравнений, необходимых для нахождения наибольшего элемента из 4 отдельных элементов? Я знаю, что для 5 разных чисел это 6, пол (5/2) * 3; это из книги clrs. но я знаю, что нет никакой общей формулы для поиска этого или есть?

редактировать осветление

эти 4 элементов могут быть в любом другом порядке (для всех перестановок из этих 4-х элементов) им не заинтересованы в методике подсчета, чтобы следить за наибольший элемент, как вы траверс элементов, но сравнения вроде> или <.

Answer 1

для 4 элементов мин. число сравнений 3.

В общем, чтобы найти самый большой из N элементов, которые вам нужны N-1 сравнения. Это дает вам 4 5 цифр, а не 6.

Доказательство:

1. всегда есть решение с N-1 сравнения: просто сравнить первые два, а затем выбрать больше и сравнить с следующей, выберите больше и сравните со следующим и т. д.

2. не может быть более коротким решением, потому что это решение не будет сравнивать все элементы.

QED.

Answer 2

Подумайте об этом как о конкуренции. Сравнивая два элемента, у вас есть слабее и победитель.

Итак, если у вас есть n элементов и вам нужен 1 окончательный победитель, вам нужно сравнить n-1, чтобы исключить другие.

Answer 3

для элементов A, B, C, D

, если A> B + C + D, то требуется только одно сравнение, чтобы знать, что является самым большим.

Вам все равно придется повезти.

Answer 4

Я знаю, что он не отвечает на исходный вопрос, но мне понравилось читать этот не-интуитивный пост на the minimum number of comparisons needed to find the smallest AND the largest number from an unsorted array (с доказательством).