количество сравнений в одновременном максимального и минимального элемента

Question

Это вопрос, который я пытаюсь решить:

---

Следующий алгоритм разделяй и властвуй предлагается найти одновременное максимальное и минимальное:

• Если есть один элемент, то максимальное и минимальное

• если есть два пункта, а затем сравнить их и в одном из сравнения вы можете найти й е максимум и минимум.

• В противном случае разделите вход в две половины, разделенные как равномерно (если N нечетно, одна из двух половин будет иметь еще один элемент, чем другой).

• Рекурсивно найти максимум и минимум каждой половины, а затем в двух дополнительных сопоставлениях произвести максимум и минимум для всей проблемы.

(b) Предположим, что N имеет вид 3 + 2k. Каково точное количество сравнений, используемых этим алгоритмом?

---

для этого пункта (b), я попытался найти уравнение рекурсии для решения, но это не сработало. Я попытался

T(n)= T(n/2+1) + T(n/2) + 3 

где три минимальная стоимость при попытке 3 входа. любая помощь?

Answer 1

Ваше рецидивы уравнение не должны иметь срок для частного случая п = 3. Алгоритм дает следующие факты:

• T (1) = 0
• T (2) = 1
• Т (п) (п> 2) = T (пол (п/2)) + T (CEIL (п/2)) + 2

Это должно быть все, что вам нужно выработать ответ ,