pro.algorithms
Привет, Как оптимально можно вычислять детерминат матрицу, которые элементы
{0, 1} ноль или единица, при этом разница кол.во 1 и сторону матрицу не так большой ( <= 50 ), но саму сторону матрицу очень большой ~ 200 000
Edit: Забыл сказать, матрица - симметричен по основному диагоналу, то есть для любой 1 <= i , j <= n , a[ i ][ j ] == a[ j ][ i ]
a[ i ][ i ] == 0
?
9 ответов
Ничего не понял
Khurshid
Автор вопроса
Ничего не понял
Есть квадратная симметричная матрица N x N, состоит только из 0 или 1. Нужен вычислять детерминант. 1 <= N <= 200 000, Но кол.во 1 в матрице не больше N + 50. Нужен вычислять детерминант матрицу.
Khurshid
Автор вопроса
Есть квадратная симметричная матрица N x N, состо...
Наивный метод вроде O(N^3) — если не ошибаюсь. Но мне нужен максимум за O(N) or O(N*log(N)) .
Наивный метод вроде O(N^3) — если не ошибаюсь. Но ...
А откуда такая задача?
Khurshid
Автор вопроса
А откуда такая задача?
acm.timus.ru ) 2147
Знаешь определение детерминанта через детерминанты подматриц при разбиении через строки/столбцы?
Khurshid
Автор вопроса
Знаешь определение детерминанта через детерминанты...
Да знаю, Det(A) = sum( (-1)^(j+1) * a[1][j] * M(1,j), j = 1..N) ?
Да знаю, Det(A) = sum( (-1)^(j+1) * a[1][j] *...
Что такое M(1,j)?
Наивный метод вроде O(N^3) — если не ошибаюсь. Но ...
Эм, даже элементы посмотреть уже квадрат
Похожие вопросы
Обсуждают сегодня