Корректность жадного алгоритма

1. Правильность:

   • Предположим, что максимальное количество пар, которые можно удалить, равно k. Утверждение: существует оптимальное решение, в котором первые элементы всех пар являются k наименьшими элементами массива. Доказательство: я покажу, что любое решение можно преобразовать в такое, которое содержит первые k элементов в качестве первых элементов всех пар.

     1. Предположим, что у нас есть две пары (a, b), (c, d) такие, что a <= b <= c <= d, 2 * a <= b и 2 * c <= d. В этом случае также допустимы пары (a, c) и (b, d). И теперь у нас есть a <= c <= b <= d. Таким образом, мы всегда можем преобразовать пары так, чтобы первый элемент любой пары не был больше второго элемента любой пары.

     2. Когда у нас есть это свойство, мы можем просто заменить наименьший элемент среди всех первых всех элементов всех пар на наименьший элемент в массиве, второй наименьший среди всех первых элементов - на второй наименьший элемент в массиве и так далее без инвалидации любая пара.

   • Теперь мы знаем, что существует оптимальное решение, содержащее k наименьших элементов. Понятно, что мы не можем ухудшить ответ, взяв наименьший неиспользуемый элемент (увеличение его может только уменьшить ответ для следующих элементов), который подходит каждому из них. Таким образом, это решение является правильным.

   • Замечание на случай, когда длина массива нечетная: неважно, куда идет средний элемент: в первую или во вторую половину. В первой половине бесполезно(во второй половине не хватает элементов). Если ставить на вторую половину, то это бесполезно два(допустим, что взяли. Это значит, что где-то во второй половине есть "свободное место". Таким образом, мы можем сдвинуть некоторые элементы на единицу и избавиться от него ).

2. Оптимальность с точки зрения временной сложности: временная сложность этого решения равна O(n). Мы не можем найти ответ, не прочитав весь ввод в худшем случае, а чтение занимает уже O(n) времени. Таким образом, данный алгоритм является оптимальным.

Предположим ваш метод. Индексы отсчитываются от 0.

Обозначим в общем:

• end_1 = floor(N/2) граница (включительно) первой части.

Обозначим при итерации:

• i индекс в первой части, j индекс во второй части,
• оптимальное решение до этого момента sol(i,j) (используя алгоритм спереди),
• пары, которые остаются оптимально спаренными за (i,j) точкой, т. е. от (i+1,j+1) и далее rem(i,j) (можно рассчитать с помощью алгоритма сзади),
• окончательное оптимальное решение может быть выражено как функция любой точки как sol(i,j) + rem(i,j).

Наблюдение №1: при выполнении алгоритма спереди используются все точки из [0, i] диапазона, некоторые точки из [end_1+1, j] диапазона не используются (мы пропускаем a(j) не достаточно большой). При выполнении алгоритма сзади некоторые [i+1, end_1] точек не используются, а используются все [j+1, N] точек (недостаточно малое a(i) пропускаем).

Наблюдение №2: rem(i,j) >= rem(i,j+1), потому что rem(i,j) = rem(i,j+1) + M, где M может быть 0 или 1 в зависимости от того, можем ли мы соединить a(j) с каким-то неиспользуемым элементом из диапазона [i+1, end_1].

Аргумент (от противного): предположим, что 2*a(i) <= a(j) и что отсутствие объединения a(i) и a(j) в пару дает как минимум такое же хорошее окончательное решение. Далее по алгоритму мы попытаемся соединить a(i) и a(j+1) в пары. С:

• rem(i,j) >= rem(i,j+1) (см. выше),
• sol(i,j+1) = sol(i,j) (поскольку мы не объединили a(i) и a(j) в пару)

мы получаем, что sol(i,j) + rem(i,j) >= sol(i,j+1) + rem(i,j+1) что противоречит предположению.