Это будет довольно большой вопрос от меня, поскольку он требует глубокого и тщательного понимания проблемы, а также различных подходов, используемых до сих пор для оптимального решения.
В связи с этим я создам блог позже, так как с моей стороны требуется немного времени, чтобы написать содержание и так далее. Итак, я предоставлю ссылку на свой блог, как только он будет готов.
Тем не менее, я публикую это, чтобы мы могли начать обсуждение.
Первое первым:
Проблема заключается в следующем:
Напишите эффективный алгоритм, который ищет значение в таблице размера n x m (двумерный >массив). Эта таблица отсортирована по строкам и столбцам, т. е.
Таблица[i][j] ≤ Таблица[i][j + 1] Таблица[i][j] ≤ Таблица[i + 1][j].
Здесь следует отметить, что все строки и столбцы сортируются монотонно, т. е. все строки и столбцы сортируются в неубывающем (лексикографическом) порядке.
Чтобы узнать о реальной проблеме и приятном обсуждении этой проблемы, нажмите на следующую ссылку:
Примечание: этот пост состоит из частей 1, 2 и 3.
Хонг Шен из Университета Гриффита, Австралия, 27 декабря 1995 г. опубликовал оптимальное решение этой задачи, равное O(mlog(2n/m)) для последовательного алгоритма.
Hong Shen-- Обобщенная Оптимальная матрица Поиск < /а>
С тех пор по этому поводу было сделано множество дискуссий на форумах, в блогах, а также онлайн и офлайн статей и публикаций, но на сегодняшний день, насколько мне известно, 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);
}
Если вам нужен весь исполняемый код, сообщите мне.
Спасибо за ваше терпение и помощь и увидимся на доске обсуждений:
Примечание: @ Администраторы или модераторы, дайте мне знать, если это не подходящее место для такого длинного вопроса, тогда я перейду в свой блог.
