Поиск в матрице — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Задача
 
{{Задача
|definition = Задана двумерная матрица, состоящая из n строк и m столбцов. Необходимо найти расположение указанного элемента в матрице или определить, что данный элемент в матрице отсутствует.  
+
|definition = Задана отсортированная двумерная матрица, состоящая из n строк и m столбцов. Необходимо найти расположение указанного элемента в матрице или определить, что данный элемент в матрице отсутствует.  
 
}}
 
}}
  
  
 +
{{Определение
 +
|id=def1
 +
|definition=Отсортированная матрица - матрица, для которой выполнено следующее условие: <tex> a[row][col] \le a[row + 1][col], a[row][col] \le a[row][col + 1] </tex>
 +
}}
 
== Решение за O(n<tex>\cdot</tex>m) ==
 
== Решение за O(n<tex>\cdot</tex>m) ==
 
Для начала рассмотрим наивный алгоритм поиска элемента. В каждой строке исходной матрицы запускаем линейный поиск, если находим элемент, то возвращаем его координаты <tex>(row, col)</tex>. Время работы — <tex>O(n \cdot m)</tex>.
 
Для начала рассмотрим наивный алгоритм поиска элемента. В каждой строке исходной матрицы запускаем линейный поиск, если находим элемент, то возвращаем его координаты <tex>(row, col)</tex>. Время работы — <tex>O(n \cdot m)</tex>.

Версия 15:01, 10 января 2016

Задача:
Задана отсортированная двумерная матрица, состоящая из n строк и m столбцов. Необходимо найти расположение указанного элемента в матрице или определить, что данный элемент в матрице отсутствует.



Определение:
Отсортированная матрица - матрица, для которой выполнено следующее условие: [math] a[row][col] \le a[row + 1][col], a[row][col] \le a[row][col + 1] [/math]

Решение за O(n[math]\cdot[/math]m)

Для начала рассмотрим наивный алгоритм поиска элемента. В каждой строке исходной матрицы запускаем линейный поиск, если находим элемент, то возвращаем его координаты [math](row, col)[/math]. Время работы — [math]O(n \cdot m)[/math].


Решение за O(n[math]\cdot[/math]log(m))

Данный способ решения использует наивное решение за [math]n \cdot m[/math], улучшенное с помощью двоичного поиска. Для этого в каждой строке запускается двоичный поиск. Время работы — [math]O(n \cdot log(m)[/math].

Замечание

Время работы может быть улучшено до [math]O(min(n, m) \cdot log(max(n \cdot m))[/math]. Для этого необходимо модифицировать алгоритм так, чтобы в том случае, если столбцов больше чем строк, он бы запускал двоичный поиск по строкам, если строк больше — наоборот.