2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Поиск двух элементов приближающих число в матрице
Сообщение06.07.2016, 17:42 
Дана матрица $n \times n$, каждая строка и каждый столбец которой упорядочены по возрастанию. Предложите алгоритм, находящий два элемента этой матрицы, сумма которых наиболее близка к заданному числу q. Ограничение по дополнительной памяти — $O(n)$. Изменять исходную матрицу нельзя. Оценка будет зависеть от эффективности вашего алгоритма.

Собственно, понятно, что можно перебрать все пары чисел за $O(n^{4})$. Но сдается мне, что авторы задачи не этого хотят :facepalm:
Как думаете, насколько быстрым можно сделать алгоритм(и как)?
Также, если Вы знаете литературу, которая по вашему мнению может помочь мне прозреть, буду благодарна за ссылки.

 
 
 
 Re: Поиск двух элементов приближающих число в матрице
Сообщение06.07.2016, 17:53 
Аватара пользователя
Тупой перебор не учитывает условия
arien в сообщении #1136190 писал(а):
каждая строка и каждый столбец которой упорядочены по возрастанию.

Упорядоченность элементов позволяет организовать что-то наподобие метода "вилки". Например, начать с суммы элементов из "середины" матрицы, тогда будет ясно, какие суммы заведомо не имеет смысла брать.

 
 
 
 Re: Поиск двух элементов приближающих число в матрице
Сообщение06.07.2016, 18:07 
Аватара пользователя
Есть довольно очевидный способ за $O(n^3)$ (стандартный способ поиска элемента в матрице, упорядоченной по строкам и столбцам - смотрим в правый верхний угол, откидываем либо один столбец, либо одну строку).

 
 
 
 Re: Поиск двух элементов приближающих число в матрице
Сообщение06.07.2016, 18:31 
mihaild в сообщении #1136198 писал(а):
Есть довольно очевидный способ за $O(n^3)$ (стандартный способ поиска элемента в матрице, упорядоченной по строкам и столбцам - смотрим в правый верхний угол, откидываем либо один столбец, либо одну строку).

То есть идем по всем элементам матрицы, и для каждого ищем ближайший к q-$a_{ij}$ элемент за $O(n)$.. Да, это уже хорошо, но интересно, можно ли сделать быстрее?

 
 
 
 Re: Поиск двух элементов приближающих число в матрице
Сообщение06.07.2016, 18:47 
Если каждый раз искать с нуля то $O(n^3)$, но можно перебрать элементы по возрастанию за $O(n^2\ln(n))$ и с другой стороны - по убыванию за те же $O(n^2\ln(n))$. Для этого потребуется дополнительная память $O(n)$.

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group