Тема: Каков оптимальный алгоритм поиска седловой точки в матрице?

[Mrrl›]

Посмотрел я программу этого курса (МОР). Очень интересно. Но неужели там действительно рассматриваются эффективные (быстрее, чем за N^2) алгоритмы работы с матрицами? Задача ведь совершенно не практическая - какой смысл обрабатывать матрицу быстрее, чем ее можно построить?

               

               

[Bindaree›]

*нервно*

ничего не знаю про программу

               

               

[Арвинд›]

Нет, думаю, что не рассматриваются. По крайней мере нам Васильев в "методах оптимизации" этого не рассказывал точно, а экономисты наверняка меньше материала проходят. Думаю, если решение нашей задачи где-то и есть, то не в популярных учебниках, а в статьях - и скорее по тематике "численные методы".

               

               

[Mrrl›]

Может быть, и там. Но по-моему, в численных методах дальше быстрого преобразования Фурье не идут. По той же причине - непрактично. Быстрое умножение матриц и полиномов, быстрая и сверхбыстрая длинная арифметика - компьютерная алгебра этим занимается наверняка, а кто еще?

               

               

[Арвинд›]

Да, больше вроде некому.


Вопрос по предложенному алгоритму (я так и не разглядел его в деталях): оценка-то какая в итоге?
Она лучше или хуже, чем сумма (по i от 1 до n)  i*log i ?
Потому что мне (очень смутно) кажется, что с оценкой в виде такой суммы алгоритм можно придумать.
Плюс еще линейная добавка, конечно.

               

               

[Mrrl›]

Оценка такая:

n*sqrt(2*log₂n)*2^sqrt(2*log₂n)

Это лучше, чем n^(1+eps), но хуже, чем n*log(n)^M
(при любых eps>0, M<infinity)

А sum(i*log(i)) - это больше, чем n². Не играет

               

               

[Арвинд›]

Цитата из: Mrrl on 27-12-2005, 20:05:14
А sum(i*log(i)) - это больше, чем n². Не играет
Логично, блин. Что-то я сильно тормознул.

Однако, оценка n*sqrt(2*log2n)*2^sqrt(2*log2n) приводилась вроде бы до того, как алгоритм был дополнен линейным поиском с.т. по значению (CheckVal)? Значит, теперь, если аккуратно считать, должно получиться больше.
Извиняюсь, что задаю вопрос, не разобравшись 

               

               

[Mrrl›]

Нет, CheckVal предусматривался с самого начала. Это не поиск, а проверка одного значения за O(n) операций. У алгоритма изменилась семантика некоторых шагов (работа со значением седловой точки вместо индексов), но сложность осталась той же.