Участник:Zerika

Свойства и структура алгоритма

Общее описание алгоритма

Данный алгоритм предназначен для поиска седловой точки в числовой матрице A. Седловой точкой называется элемент матрицы, который одновременно является минимальным в своей строке и максимальным в своем столбце. Алгоритм является прямым (не итерационным) и детерминированным. Его суть заключается в последовательном сканировании строк матрицы для поиска минимумов, а затем в проверке этих кандидатов на максимальность в соответствующих столбцах. В матрице может быть несколько седловых точек или не быть ни одной.

Математическое описание

Пусть задана матрица A размерности m x n (m строк, n столбцов).

Элемент A_ij является седловой точкой, если выполняются два условия:

Он является минимальным элементом в своей строке i:

A_ij = min A_ik, k от 1 до n

Он является максимальным элементом в своем столбце j:

A_ij = max A_dj, d от 1 до m

Алгоритм можно описать как поиск таких индексов (i, j), для которых:

∀k: A_ij ≤ A_ik и ∀d: A_ij ≥ A_dj

Вычислительное ядро алгоритма

Вычислительное ядро алгоритма состоит из двух последовательных этапов:

Поиск минимумов в строках, в котором для каждой строки i матрицы A последовательно сравниваются элементы A_ij с текущим минимумом, и при нахождении меньшего значения обновляются минимальный элемент и его позиция столбец (d).

Проверка кандидатов в столбцах d, в котором для каждого найденного минимума строки последовательно сравниваются элементы A_id соответствующего столбца с кандидатом, и при обнаружении большего элемента проверка прекращается.

Макроструктура алгоритма

Алгоритм состоит из двух последовательных макроопераций:

2. Поиск минимума в каждой строке матрицы. Эта операция представляет собой цикл по всем строкам, внутри которого выполняется сканирование элементов строки.

1. Проверка найденных кандидатов на максимальность в их столбцах. Эта операция представляет собой цикл по всем строкам-кандидатам, внутри которого для каждого кандидата выполняется полный проход по его столбцу.

Последовательная сложность алгоритма

Поиск минимумов в строках: Требуется просмотреть каждый элемент матрицы ровно один раз. Сложность = O(m * n).

Проверка кандидатов: В худшем случае (когда все минимумы строк находятся в разных столбцах) требуется для каждой из m строк проверить m элементов в столбце. Сложность = O(m * m) = O(m^2).

Общая последовательная сложность: O(m * n) + O(m^2). В худшем случае, когда матрица квадратная (m = n), сложность составляет O(n^2) + O(n^2) = O(n^2)