1. "То есть, допустим, две оказались в текущем квадрате седловыми?"
Как мы знаем, если две точки оказались седловыми, то значения в них одинаковы. Поэтому я предлагаю на каждом этапе искать не саму седловую точку, а только ее значение. На каждом шаге алгоритма у нас будут три кандидата на значения седловых точек (те, что вернулись из трех под-подматриц), и нам нужно проверить, какое из них может оказаться значением седловой точки для нашей подматрицы. Для этого можно воспользоваться следующим алгоритмом (сравнивающим значение седловой точки, если она есть, с поданным значением a):
int CheckVal(double [,]M,int m,int n,double a,out int iv,out int jv){
iv=jv=0;
int i1=0,j1=0;
while(i1<m && j1<n){
if(M[i1,j1]>a) j1++; else i1++;
}
if(i1==m) return 1; // a>val
int i2=0,j2=0;
while(i2<m && j2<n){
if(M[i2,j2]>=a) j2++; else i2++;
}
if(j2==n) return -1; // a<val
iv=i1; jv=j2; // some saddle point
return 0;
}
Алгоритм выдает -1,0 или 1, если a меньше, равно или больше значения седловой точки соответственно. Если выдано 0, то в параметрах iv, jv выдаются координаты потенциальной седловой точки (если хотя бы одна седловая точка со значением a есть, то гарантируется, что (iv,jv) - одна из них).
2. Действительно, можно ничего не проверять. Если в подматрице все диагональные элементы одинаковы, то их значение - единственный кандидат на значение седловой точки. Его и вернем.
3. "Обычный метод" - деление пополам или что-то еще?
Пусть f(n) - число операций, необходимое для поиска седловой точки. Пусть мы умеем искать медиану (и более широко - k-е по порядку значение из массива) + сортировать массив на "большие - меньшие" за C*n операций.
В случае деления пополам получаем:
f(n)=3*f(n/2)+n*(C+4)
(здесь 4*n - наихудшее время работы функции CheckVal).
Очевидно, что f(n)=D*n^(ln(3)/ln(2)), где D - некоторая константа.
Пусть рекурсия неравномерна. Для нее
f(n)=f(n-n1)+2*f(n1)+n*(2*C+4)
2*C понадобилось, поскольку диагональные элементы делятся на части дважды. Можно проверить, что если
n1=n/2^(sqrt(2*log(n)-1/2), то f(n)<D*n*sqrt(2*log(n))*2^sqrt(2*log(n))
(но это примерно страница выкладок). А это функция растет медленнее любой степенной (c показателем, большим 1).
В общем, дело в формуле f(n)=f(n-n1)+2*f(n1)+n*(2*C+4), точнее, в коэффициенте 2 перед f(n1). Поскольку f(n) выпукла вниз, для минимизации этого выражения требуется, чтобы выполнялось условие n1<n-n1. Точнее, f'(n-n1)=2*f'(n), а из-за медленного роста f(n)/n получаем, что n1 гораздо меньше n-n1.
