Доказать оптимальность алгоритма

[Legioner93]

Что-то совсем туплю, с виду простая задача. Предлагается такой алгоритм одновременного поиска минимума и максимума в массиве: сначала разбиваем массив на пары, сравниваем два элемента в каждой паре между собой, потом сравниваем меньший с текущим минимумом, а больший - с текущим максимумом. Количество сравнений в таком алгоритме $\left\lceil\frac{3n}{2}\right\rceil-2$.
Нужно доказать, что в общем случае быстрее решить задачу нельзя.
Источник: "Алгоритмы" Кормен, 9.1-2.

[Legioner93]

Может, есть какие-нибудь хотя бы идеи?
У меня предлагается решить эту задачу таким способом:

Терминология:
$a$ - число элементов массива, которые ещё ни разу ни с кем не сравнивались
$b$ - число элементов массива, которые были больше во всех сравнениях
$c$ - число элементов массива, которые были меньше во всех сравнениях
$d$ - число элементов массива, которые были и больше и меньше.
Конфигурацией называется четверка чисел $(a,b,c,d)$. Начальная конфигурация $(n,0,0,0)$, конечная $(0,1,1,n-2)$.
Потенциальной функцией называется функция $f=f(a,b,c,d)$

А решить задачу предлагается так. Найти некоторую потенциальную функцию $f=f(a,b,c,d)$, которая изменяется при любом сравнении не более, чем на величину $k$ (например на единицу). И тогда, если выполняется $f(0,1,1,n-2)-f(n,0,0,0) \geqslant \left(\left\lceil\frac{3n}{2}\right\rceil-2\right) \cdot k$, то отсюда сразу следует, что любой алгоритм такого поиска требует не менее $\left\lceil\frac{3n}{2}\right\rceil-2$ сравнений.

Осталось вроде простая задача - найти подходящую функцию. Этого я сделать не смог, может быть вы подскажете?
Кстати, для поиска минимального элемента $f=a+c$ (с определенными оговорками насчёт существования двух и более минимальных элементов, но не суть).

[Cash]

Если взять $f(a,b,c,d) = a+2b+2c+4d$
Тогда сравнивая "новые" мы уменьшаем $a$ на 2, увеличивая $b$ и $c$ на 1;
Сравнивая "максимумы" мы уменьшаем $b$ на 1, увеличивая $d$ на 1. "Минимумы" аналогично.
Сравнивая "новый" с "максимумом" мы уменьшаем $a$ на 1, и увеличиваем на 1 либо $d$ либо $c$.
Вот и нашелся "прокол". Получается, что данным способом не получится никак доказать оптимальность.
При таком алгоритме: берем "новый" элемент и сравниваем его с текущим максимумом. И нам может повезти и мы за $n$ сравнений перекидаем всю кучу.

[Sonic86]

Legioner93 в сообщении #690631 писал(а):

Количество сравнений в таком алгоритме $\left\lceil\frac{3n}{2}\right\rceil-2$.
Нужно доказать, что в общем случае быстрее решить задачу нельзя.

Че-то непонятно. Возьмем самый тупой алгоритм:

imax=A[0];
imin=A[0];
for(j=0;j<n;j++){
  if(A[j]>imax){
    imax=A[j];
  }
  else{
    if(A[j]<imin){
      imin=A[j];
    }
  }
}

Легко подобрать такие массивы (отсортированный прямо и отсортированный обратно), что число сравнений меняется от $n+O(1)$ до $2n+O(1)$.
Что такое "в общем случае"?
А!
Т.е. надо доказать, что для любого массива время поиска максимума и минимума $\geqslant\frac{3}{2}n+O(1)$?

[Cash]

Или внести уточнение - изменением потенциальной функции считать наименьшее из возможных приростов в результате какого-то сравнения. Тогда вроде проходим...

[Legioner93]

Sonic86 в сообщении #691194 писал(а):

Т.е. надо доказать, что для любого массива время поиска максимума и минимума $\geqslant\frac{3}{2}n+O(1)$?

Нужно доказать, что для любого алгоритма поиска существуют входные данные, на которых он работает не быстрее, чем за $\left\lceil\frac{3n}{2}\right\rceil-2$.
Авторская формулировка (Кормен) : "Покажите, что в наихудшем случае для поиска ..., необходимо выполнить $\left\lceil\frac{3n}{2}\right\rceil-2$ сравнений"

Это как с сортировкой. Да, иногда мы может упорядочить массив за $O(n)$, но лишь иногда.

Cash
Сейчас вам отвечу тоже:)

[Sonic86]

Я попробовал посчитать среднее число сравнений для моего алгоритма, для алгоритма из Кормена, для модифицированного алгоритма Кормена (двойки заменил на тройки) и для бинарного поиска максимума и минимума. Везде получается $\frac{3}{2}n+O(1)$. Это неспроста явно

[Cash]

Если мы не делаем глупостей - то есть не берем в сравнения элементы из подмножества 4) в классификацииLegioner93 из 2-го поста, то мы увеличиваем потенциальную функцию $f(a,b,c,d) = a+2b+2c+4d$ на 2 в среднем при любом сравнении.

[Legioner93]

Cash в сообщении #691244 писал(а):

Если мы не делаем глупостей - то есть не берем...

Такие обороты явно запрещены в моём задании:

Цитата:

В тексте можно использовать только аргументы, относящиеся к потенциальной функции. Нельзя апеллировать к авторскому представлению о том, что какие-то действия "неоптимальные"

Вы же понимаете, что выражение "делаем глупости" использовать ну никак нельзя.

Вашу функцию, которая равна $f=2d-a$ (если забить на константу и вспомнить, что $a+b+c+d=n$), я нашел уже давно, и она действительно почти подходит. Вот если ещё удастся это почти как-то по-божески обосновать... Что-нибудь вроде: если мы в одном месте увеличили такую функцию на 3 глупым или на 4 (такой вариант тоже возможен) очень глупым сравнением, то где-нибудь потом обязательно она увеличится всего лишь на 1 и на 0 соответственно, что в среднем даст нам те самые 2. Но ничего такого мне доказать не удалось.

Более того, я доказал, что ни одна линейная функция не является ответом на задачу, если не использовать какие-нибудь вот такие пасы руками про глупые сравнения. Но их никто не запрещает использовать, если всё удастся формально изложить.
Про нелинейные функции мне неизвестно ничего.

UPD: Что значит "увеличиваем в среднем"? Нужно брать максимальное увеличение. И функция может увеличиться и на 3, и на 4, даже если не брать элементы из множества $d$. Например мы сравнили кандидата на максимум и кандидата на минимум и вышло, что первый меньше второго. Тогда функция увеличится аж на 4.

-- Пн мар 04, 2013 23:09:01 --

Cash в сообщении #691202 писал(а):

Или внести уточнение - изменением потенциальной функции считать наименьшее из возможных приростов в результате какого-то сравнения.

Нет, так нельзя. Как минимум потому, что результаты сравнений не независимы. То есть вовсе не значит, что для любого алгоритма существует вход, на котором изменение потенциальной функции и правда будет равно минимуму во всех сравнениях.

[Cash]

Legioner93 в сообщении #691250 писал(а):

:D Такие обороты явно запрещены в моём задании:

Мне никто и ничего не запрещал и запретить не может. Под глупостями я понимаю сравнения, либо не увеличивающие потенциальную функцию, либо увеличивающие ее на величину меньшую, чем прочие сравнения. Нарушений строгости здесь никаких нет.

Legioner93 в сообщении #691250 писал(а):

Нужно брать максимальное увеличение.

Ну получите в таком случае, что существует алгоритм, который в некоторых случаях сможет справиться за $n$ сравнений, что полностью согласуется с практикой.
Как-то вам нужно определиться между

Legioner93 в сообщении #691209 писал(а):

"Покажите, что в наихудшем случае для поиска ...,

и этим

Legioner93 в сообщении #691250 писал(а):

Нужно брать максимальное увеличение.

[Legioner93]

А, так вы это имели в виду, говоря о глупостях. Прошу прощения, не понял.
Да, действительно, я написал противоречие, сейчас исправлюсь.
Нужно показать, что для любого алгоритма найдется хотя бы один вход, на котором эта потенциальная функция увеличивается не более, чем на 2 каждый раз. Вы можете это сделать?
Другими словами, нужно исключить ситуацию существования алгоритма, который при любом входе хоть разок возьмет да и увеличит функцию на 3, а то и на 4.

[Sonic86]

Проверьте.
Я только коэффициент получу. Делаем через указание автора.
Пусть $k$ - номер шага. Число элементов в массиве равно $2n$.
$a_k$ - число элементов, которые еще ни разу ни с кем не сравнивались
$b_k$ - число элементов, которые может быть могут быть минимальными, но уже не могут быть максимальными
$c_k$ - число элементов, которые может быть могут быть максимальными, но уже не могут быть минимальными
$d_k$ - число элементов, которые уже не могут быть максимальными и не могут быть минимальными
(у Legioner93 другое описание $b,c$)
Далее, автор спрашивает, как меняются эти числа при сравнениях?
Множества элементов будем обозначать $A,B,C,D$, будем писать $x_M, y_N$ в смысле $x \in M, y\in N$, где $M,N\in \{A,B,C,D\}$
Для того, чтобы определить, как могут меняться $a_k,b_k,c_k,d_k$ надо разобрать все случаи $x_M<y_N$ для $M,N\in \{A,B,C\}$ (всего 6 случаев). Каждому сравнению $x_M<y_N$ соответствует преобразование $(a_k,b_k,c_k,d_k)\to(a_{k+1},b_{k+1},c_{k+1},d_{k+1})$. Каждому алгоритму, находящему максимум и минимум, соответствует некая последовательность сравнений. Последовательности сравнений соответствует последовательность шагов в пространстве, ведущая из точки $(n,0,0,0)$ в точку $(0,1,1,2n-2)$. Метрика в пространстве $\sum |x_i-y_i|$. Нам надо тогда доказать, что для любой последовательности сравнений существует цепочка, состоящая из $3n+O(1)$ шагов.
Разберем все случаи $x_M<y_N$. Формулы можно выписать явно:

$$1. \ x_A<y_A \to\left{ \begin{cases} a_{k+1}=a_k-2 \\ b_{k+1}=b_k+1 \\ c_{k+1}=c_k+1 \\ d_{k+1}=d_k \end{cases}$$

$$2. \ x_B<y_B \to\left{ \begin{cases} a_{k+1}=a_k \\ b_{k+1}=b_k-1 \\ c_{k+1}=c_k \\ d_{k+1}=d_k+1 \end{cases}$$

$$3. \ x_C<y_C \to\left{ \begin{cases} a_{k+1}=a_k \\ b_{k+1}=b_k \\ c_{k+1}=c_k-1 \\ d_{k+1}=d_k+1 \end{cases}$$

$$4. \ x_A*y_B \to\left{ \begin{cases} a_{k+1}=a_k -1\\ b_{k+1}=b_k+[x_A>y_B] \\ c_{k+1}=c_k \\ d_{k+1}=d_k+[x_A<y_B] \end{cases}$$

$$5. \ x_A*y_C \to\left{ \begin{cases} a_{k+1}=a_k-1 \\ b_{k+1}=b_k \\ c_{k+1}=c_k+[x_A<y_C] \\ d_{k+1}=d_k+[x_A>y_C] \end{cases}$$

$$6. \ x_B*y_C \to\left{ \begin{cases} a_{k+1}=a_k \\ b_{k+1}=b_k-[x_C<y_B] \\ c_{k+1}=c_k-[x_C<y_B] \\ d_{k+1}=d_k+2[x_C<y_B] \end{cases}$$

Здесь $[x_M<y_N]=1 \Leftrightarrow x_M<y_N$, иначе $[x_M<y_N]=0$ - нотация Айверсона.
Покажем, что имеет смысл рассматривать только случай, когда все сравнения делаются независимо. Всего 6 типов сравнений. При сравнении с элементами из $A$ у нас нет никакой информации об элементе из $A$, поэтому значения $[x_M<y_N]$ при $M=A\vee N=A$ произвольны. Далее, значение $[x_B<y_B]$ произвольно, поскольку об $x_B$ мы знаем лишь то, что $x_B$ меньше некоторого элемента, который ушел в $C$, а из $C$ потом уйдет в $D$, значит в $B$ никогда не попадет, кроме того, как только мы узнаем $[x_B<y_B]$, так сразу $x_B$ уйдет из $B$ в $D$; аналогично для $y_B$; аналогично произвольно $[x_C<y_C]$. Т.е. внутри каждого $B,C$ нет никакой информации на каждом шаге. Наконец, при выборе $x_C,y_B$ для вычисления $[x_C<y_B]$ не имеет смысла брать те $x'_C, y'_B$ для которых мы при преобразовании типа $1$ узнали, что $x'_C<y'_B$ - мы так ничего нового не узнаем, алгоритм выполнит только лишнее действие, множества $A,B,C,D$ не изменятся. А исключая этот факт, значение $[x_C<y_B]$ в остальном произвольно.
В силу независимости сравнений подберем $x_M,y_N$ в каждом шаге так, чтобы алгоритм работал медленнее всего и шел по самому длинному пути (в преобразованиях 4 и 5 подбираем элементы так, чтобы они не переходили сразу в $D$). В результате получим следующие векторы преобразований:
$1. \ (-2,1,1,0)$
$2. \ (-1,0,1,0)$
$3. \ (-1,1,0,0)$
$4. \ (0,-1,0,1)$
$5. \ (0,0,-1,1)$
$6. \ (0,0,0,0)$
Суммируем еще 2-ю и 3-ю координату, выкинем линейно зависимые вектора, получим в 3-хмерном пространстве лишь $(-2,2,0), (-1,1,0), (0,-1,1)$. Здесь оптимальный путь единственен - $n$ раз 1-е преобразование и $2n$ раз 2-е. При подъеме пути обратно из 3-хмерного в 4-хмерное пространство длина пути сохранится та же. Значит для поиска максимума и минимума в массиве длиной $2n$ надо в худшем случае $3n$ сравнений, отсюда получаем число сравнений $\frac{3}{2}n+O(1)$.

(Оффтоп)

У меня, кстати, Кормен другой, у меня номер упражнения 10.1-2*