Анализ временной сложности по задаче оптимального матричного поиска (2D) - PullRequest
Новая
       27

Анализ временной сложности по задаче оптимального матричного поиска (2D)

1 голос
/ 19 июня 2011

Это будет довольно большой вопрос с моей стороны, поскольку он требует глубокого и глубокого понимания проблемы, а также различных подходов, используемых до настоящего времени для оптимального решения.

В связи с этим позже я создам блог по этому вопросу, поскольку для написания содержимого и т. Д. Мне потребуется немного времени со стороны, поэтому я предоставлю ссылку на свой блог, как только она будет готова.

Тем не менее, я публикую это, чтобы мы могли начать обсуждение.

Первым делом первым:

Проблема заключается в следующем:

Напишите эффективный алгоритм, который ищет значение в таблице n x m (двумерный> массив). Эта таблица отсортирована по строкам и столбцам - то есть

Таблица [i] [j] ≤ Таблица [i] [j + 1] Таблица [i] [j] ≤ Таблица [i + 1] [j].

Здесь следует отметить, что все строки и столбцы монотонно сортируются, т.е. все строки и столбцы сортируются в неубывающем (лексикографическом) порядке.

Чтобы ознакомиться с актуальной проблемой и обсудить ее, перейдите по следующей ссылке:

Примечание: у этого поста есть части 1,2 и 3.

Поиск 2D матрицы

Хонг Шен из Университета Гриффита, Австралия, 27 декабря 1995 г. опубликовал оптимальное решение для этой задачи - O (mlog (2n / m)) для последовательного алгоритма.

Хонг Шен - Обобщенный поиск оптимальной матрицы

С тех пор по этому вопросу было проведено множество дискуссий, блогов, а также статей и публикаций в Интернете и офлайн, но на сегодняшний день, насколько я знаю, O (((log (n)) 2) является лучше всего заявлено на этой статье с Улучшенный бинарный поиск .

Хотя подробный алгоритм не был предоставлен.

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

Однако я не так хорош в анализе временных сложностей алгоритмов.

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

Вот первый пример анализа сложности времени 

  /*  NIAZ MOHAMMAD

    IntPol2d.cpp

    1. Find the interpolated mid along column
    2. Compare key with each elements in row-wise 
       along the found mid column
    3. IF failed
        DO 
        RECURSIVE call to IntPol2d 
        a. IF(key > a[row][mid])
            THEN SET l = mid + 1 and d = row - 1;
        b. ELSE set r = mid -1 and u = row;
*/


    bool intPol2d(int mat[][6], int M, int N, int target, int l, int u, int r, int d, int &targetRow, int &targetCol,int &count) {
      count++;
      if (l > r || u > d) return false;

      if (target < mat[u][l] || target > mat[d][r]) return false;

      int mid = l + ((target - mat[u][l])*(r-l))/(mat[d][r]-mat[u][l]);
      int row = u;

      while (row <= d && mat[row][mid] <= target) 
      {
        if (mat[row][mid] == target) 
        {
          targetRow = row;
          targetCol = mid;
          return true;
        }
        row++;
      }
      return intPol2d(mat, M, N, target, mid+1, u, r, row-1, targetRow, targetCol,count) ||
             intPol2d(mat, M, N, target, l, row, mid-1, d, targetRow, targetCol,count);

    }

Если вам требуется весь исполняемый код, пожалуйста, дайте мне знать .

Спасибо за ваше терпение и помощь и увидимся на форуме:

Примечание: @ Администраторы или модераторы, дайте мне знать, если это неправильное место для такого длинного вопроса, тогда я перейду к своему блогу.

1 Ответ

0 голосов
/ 17 октября 2011

вам не нужно рассматривать массив как двумерную вещь.Это просто мат [n], где n = MxN и выполняется двоичный поиск со сложностью O (log (n)).обратите внимание, что это база журнала 2 и это худший случай.Обратите внимание, что сложности не включают в себя константы, отличные от 1, потому что они не меняются в зависимости от размера ввода.Фактически наихудший случай - 2 * log (n) проверенных элемента.Кроме того, вы можете ударить тот, который вы хотите в первом тесте.Вы не можете получить быстрее, чем это без предварительной сборки хеш-таблицы или другого ассоциативного массива, где указатель на элемент в исходной матрице, которую вы ищете, находится по индексу в новом массиве.Вам нужен элемент со значением 46, поэтому вы смотрите в своей индексной таблице на индекс элемента 46, который, скажем, указывает на (M, N) = (2357 656).Бум, сложность O (1) после построения многоразовой, дорогостоящей памяти, индексной таблицы.

...