Как можно объяснить нецелое число сравнений в min-max принципом «разделяй и властвуй»?

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


algorithm minmax divide-and-conquer
person kesarling    schedule 20.04.2020    source источник
comment
О чем ты говоришь? min-max и "разделяй и властвуй" - это методы/алгоритмы решения проблем, сравнения не являются их основным кирпичиком...   -  person Jean-Baptiste Yunès    schedule 20.04.2020
comment
Вопрос не в основных кирпичиках или строительных блоках, на самом деле он очень прост. Я думаю, вы неправильно прочитали вопрос :)   -  person kesarling    schedule 20.04.2020
comment
@ Jean-BaptisteYunès, и не забывайте, что сама причина использования «разделяй и властвуй» для нахождения минимальных и максимальных чисел заключается в том, чтобы снизить сравнение. Всякий раз, когда вы не можете еще больше уменьшить сложность, всегда уменьшайте количество сравнений, это то, что я обычно слышал.   -  person kesarling    schedule 20.04.2020
comment
Я не уверен, что понимаю вашу проблему: вы пытаетесь получить минимальный и максимальный элементы массива? Или вы про алгоритм минмакс (теория игр)?   -  person Jean-Baptiste Yunès    schedule 21.04.2020
comment
@Jean-BaptisteYunès, tutorialspoint.com/design_and_analysis_of_algorithms/ Вот о чем я говорю о   -  person kesarling    schedule 21.04.2020
comment
И теория игр, то есть алгоритм minImax (min - I - max), а не minmax   -  person kesarling    schedule 21.04.2020
comment
Минимакс (иногда МинМакс), извините, но в моем районе мы всегда используем минимакс.   -  person Jean-Baptiste Yunès    schedule 21.04.2020

Ответы (1)


arrow_upward
2
arrow_downward

Подход "разделяй и властвуй" (турнир) дает ровно (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 значений.

person MBo    schedule 20.04.2020