Поиск в двумерной матрице

[frankenstein]

Назовем двумерный массив действительных чисел $A[1..n][1..n]$ возрастающим,
если для любый $k, l$ $A[k][l] \geqslant A[i][j], i \leqslant k, j \leqslant l$.
Задача поиска в квадратном возрастающем массиве формулируется так: для заданного возрастающего
массива $A[1..n][1..n]$ и некоторого числа $X$ определить, встречается ли
число $X$ в массиве $A$. Показать, что не существует алгоритма, решающего эту задачу менее чем за $n$ сравнений.

Вот как я решил это задание:
Для того чтобы определить в какой строке искать мы должны проходиться по столбцам и проверять
принадлежит ли $X$ отрезку $[A[i][0], A[i][n] ]$, если да то запускаем бинарный
поиск для данной строки, если нет идем дальше.
Если мы прошлись по всем строкам и оказалось что $X$ не лежит ни на одном
из отрезков, то такого элемента нет в массиве.
Если бинарный поиск не нашел $X$, то такого элемента нет в массиве.
В остальных случаях X содержится в массиве.
В лучшем случае сложность алгоритма составляет $O(n)$,
случай когда мы проходимся по строкам и не находим нужной строки.

Исчерпывающее ли это решение?

Сложность алгоритма составляет $O(n \log n)$

[sup]

Ваши рассуждения не доказывают, что меньше чем за $n$ сравнений (в худшем случае) найти элемент нельзя. Ну в самом деле. Как выглядит самый общий алгоритм. Берем $X$ и сравниваем с каким-то элементом матрицы. В случае совпадения - все замечательно, объект найден. Значит $X$ либо больше либо меньше того самого элемента. В каждом из этих двух случаев алгоритм имеет предписание что делать дальше. А именно, с каким новым элементом матрицы сравнивать $X$. И тд. Вы рассмотрели лишь частный случай (просмотр по строкам) при этом все равно не доказали требуемую оценку снизу. Посему задача не решена.
Могу предложить одну подсказку.
Рассмотрите "вспомогательную" диагональ. Покажите, что возможен такой случай, когда придется просмотреть все элементы стоящие на этой диагонали (а их в точности $n$).

Что касается "оптимального" алгоритма. Могу сказать следующее. Существует простой и симпатичный алгоритм, требующий не более $2n-1$ сравнений (идейно он опирается на анализ той самой диагонали, но не совсем прямолинейно). Можно ли предложить лучше - я не знаю. Есть некоторые подозрения, что нельзя. Надо бы получить алгоритм такого же типа для прямоугольных матриц, а затем попробовать доказать оптимальность по индукции. Там, правда, уже скорее всего полезет логарифм из бинарного поиска. Короче, надо разбираться.

[frankenstein]

Думаю в этой задаче надо не доказывать эту теорию, а ее опровергнуть.

Давайте определим дискретную функцию, которая принимает в качестве
своего аргумента целое число и возвращает некий элемент нашей матрицы
$f(x) = A[ \lfloor x/N \rfloor, x \mod N ]$
Что это нам даст?
Если мы будем обращаться к нашей матрице через эту функцию, то мы
можем работать с ней как если бы она была вектором, причем вектором,
элементы которого идут в неубывающем порядке.
Итак мы сводим эту задачу к задаче поиска в отсортированном массиве,
вот только размер этого массива равен $N^2$
Если применить к этому вектору бинпоиск, то сложность нашего алгоритма
составляет
$O(\log(N^2)) = O(2 \log(N)) = O(\log(N))$
Отсюда следует что существует алгоритм который требует меньше чем
n сравнений в худшем случае. Теория опровергнута.

Реализация на С++:

#include <cstdlib>
#include <iostream>
using namespace std;

template <typename vectorT>
void quick_sort(vectorT & v, const int a, const int b) {
   int i = a, j = b;
   
   // Здесь подразумевается что элементы вектора целые числа
   int x = v[ (i+j)/2 ];
   do {
      while (v[i] < x) ++i;
      while (v[j] > x) --j;

      if (i <= j) {
         if (i < j) swap(v[i], v[j]);
         ++i, --j;
      }
   } while (i <= j);

   if (i < b) quick_sort(v, i, b);
   if (a < j) quick_sort(v, a, j);
}

template <typename vectorT>
bool bin_search(vectorT & v, int size, int x) {
   int l = 0, r = size-1;

   while (l <= r) {
      int m = (l+r)/2;
      //cout << l << ' ' << m << ' ' << r << endl;

      if (x < v[m]) {
         r = m-1;
      } else if (x > v[m]) {
         l = m+1;
      } else {
         return true;
      }
   }

   return false;
}

// Инкапсуляция матрицы
template <typename T, const int N, const int M>
class matrix {
   public:
      T & operator[](int i) {
         return at(i);
      }

      // Обращение к массиву как к одномерному
      T & at(int i) {
         return a[i/M][i%M];
      }

      // Обращение к массиву как к двумерному
      T & at(int x, int y) {
         return a[x][y];
      }

   private:
      T a[N][M];
};

int main() {
   const int m_size = 3;
   matrix<int, m_size, m_size> m;

   for (int i = 0; i < m_size*m_size; ++i)
      m.at(i) = rand()%100;

   quick_sort(m, 0, m_size*m_size-1);

   for (;;) {
      for (int i = 0; i < m_size; ++i) {
         cout << "( ";
         for (int j = 0; j < m_size; ++j)
            cout << m.at(i, j) << " ";
         cout << ")\n";
      }

      int n;
      cin >> n;
      if (n == 0) break;

      if (bin_search(m, m_size*m_size, n)) {
         cout << "THERE IS" << endl;
      } else {
         cout << "THERE IS NO" << endl; 
      }
   }

   return 0;
}

[kp9r4d]

frankenstein в сообщении #843264 писал(а):

причем вектором,
элементы которого идут в неубывающем порядке.

Это неверно.

[slavav]

Предположим, что существует детерминированный алгоритм, который работает за время $o(n)$ (быстрее чем за линейное время). Под детерминированным я понимаю алгоритм, который исполняется всякий раз одинаково, если получает на вход одни и те же входные данные. Пусть такой алгоритм проделал определённое число шагов, какой будет следующий шаг?
Для детерминированного алгоритма решающего нашу задачу, это зависит только от искомого числа $x$ и тех ячеек $A$, которые он успел просмотреть до сих пор. Следовательно, если мы поменяем числа в ещё непросмотренных ячейках, то на выбор следующего шага алгоритма это не повлияет.

Если алгоритм работает за $o(n)$, то можно выбрать такое большое $n$, что алгоритм совершит менее $n$ обращений к матрице $A$.

Подадим на вход алгоритма число $x$ и матрицу $A$ такие, что
1. $n$ должно быть достаточно велико, чтобы алгоритм просмотрел менее $n$ элементов $A$
2. $A[i][j] = i + j$ вне побочной диагонали,
$A[i][j] = i + j + 1$ на побочной диагонали (на ней $i + j = n + 1$)
3. $x = n + 1$

Ясно, что $x$ в $A$ отсутствует. Алгоритм должен сказать "нет".

Запустим алгоритм, запишем все элементы к которым он обращался. Выберем непросмотренный элемент на побочной диагонали. В него впишем $x$, то есть, уменьшим на единицу. Назовём такую матрицу $B$.

Последовательность шагов детерминированного алгоритма для матриц $A$ и $B$ одинакова. Следовательно алгоритм и для матрицы $B$ ответит "нет".

Мы доказали следующее утверждение: для любого детерминированного алгоритма со временем работы $o(n)$ можно предъявить матрицу на которой он ошибётся. Противоречие, таких алгоритмов не существует.

[Lia]

slavav Ваше сообщение перемещено в Карантин: post868014.html#p868014

Запишите формулы в соответствии с требованиями Правил форума, т.е. в $\TeX$.
Краткие инструкции можно найти здесь: topic8355.html и topic183.html.
Кроме этого, в теме Видео-пособия для начинающих форумчан можно посмотреть видео-ролик "Как записывать формулы".

После того как исправите сообщение, сообщите об этом в теме Сообщение в карантине исправлено, и тогда оно будет возвращено.

[Deggial]

Пост возвращён