Как можно объяснить неинтегральное число сравнений в мин-макс разделяй и властвуй?

Question

Для наивного пути min-max сравнивает 2n-2 раз, а для разделения и завоевания - (3/2)n-2 раз. Это ровно (1/2) n сравнения меньше. Как объяснить (1/2) сравнение? Я полностью потерян (я даже не знаю, неверна ли моя интерпретация). Пожалуйста, помогите

Answer 1

Подход «разделяй и властвуй» (турнир) дает точно (3/2)n-2 сравнений, когда n - это степень двух (2,4,8,16 ...). Обратите внимание, что в этом случае (3/2)n-2 является целым числом.

Для других значений n точное число сравнений немного выше (рассмотрим простые случаи из 4,5,6,7 элементов)

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

---

Также существует метод парного сравнения - он обеспечивает (3/2)n-2 операций сравнения для четных n и (3/2)(n+1)-2 операций сравнения для нечетных n значения