Учитывая симметричную вещественную матрицу , существует ли алгоритм, который вычисляет сумму по всем 1 \ leq i <j <k \ leq n со сложностью по времени лучше, чем O (n ^ 3) ?
algorithms
time-complexity
user89217
источник
источник
Ответы:
Существует довольно практичный подход, который работает за время , где - количество бит в слове процессора. Основная идея заключается в том, что вы последовательно перебираете элементы матрицы в порядке возрастания (произвольно разрываете связи) и «включаете их». Рассмотрим момент, когда включается самый большой элемент некоторой тройки . Для простоты предположим, что указанный элемент является . Естественно добавить значение тройки к ответу сейчас, когда последний элемент включен. Таким образом, мы должны посчитать количество возможных таких, что иO(n3/w) w aij,aik,ajk aij k aik ajk уже включены (это будет количество троек, здесь - самый большой элемент, поэтому они были полностью включены только сейчас). Здесь мы можем ускорить простую реализацию , используя битовую оптимизацию.aij O(n)
За подробностями вы можете обратиться к следующей реализации в C ++ 11, которая должна работать для , (он не очень оптимизирован; однако он по-прежнему превосходит наивное суммирование для с большим отрывом, по крайней мере, на моей машине).n⩽5000 |aij|⩽109 n=5000
Если вы подумаете об обмане с оптимизацией битов, вы можете использовать метод с четырьмя русскими для получения того же результата, что дает алгоритм , который должен быть менее практичным (потому что довольно велико на большинстве современного оборудования) но теоретически лучше. Действительно, давайте выберем и сохраним каждую строку матрицы как массив целых чисел от до , где число в массив соответствует битам строки в диапазоне от включительно до исключительно вO(n3/logn) w b≈log2n ⌈nb⌉ 0 2b−1 i ib min(n,(i+1)b) 0 -indexation. Мы можем предварительно рассчитать скалярные произведения каждых двух таких блоков за времени. Обновление позиции в матрице происходит быстро, потому что мы меняем только одно целое число. Чтобы найти скалярное произведение строк и просто выполните итерацию по массивам, соответствующим этим строкам, найдите скалярные произведения соответствующих блоков в таблице и суммируйте полученные произведения.O(22bb) i j
В приведенном выше абзаце предполагается, что операции с целыми числами занимают времени. Это довольно распространенное предположение , потому что оно обычно фактически не меняет сравнительную скорость алгоритмов (например, если мы не используем это предположение, метод грубой силы фактически работает за времени (здесь мы измеряем время в битовых операциях), если принимает целочисленные значения с абсолютными значениями по крайней мере до для некоторой константы (и в противном случае мы можем решить проблему с помощью умножение матриц в любом случае), однако предложенный выше метод четырех русских использует⩽n O(1) O(n3logn) aij nε ε>0 O(nε) O(n3/logn) операции с числами размера в этом случае; поэтому он выполняет битовых операций, что все же лучше, чем грубая сила, несмотря на изменение модели).O(logn) O(n3)
Вопрос о существовании подхода все еще интересен.O(n3−ε)
Методы (битовая оптимизация и метод четырех русских), представленные в этом ответе, ни в коем случае не являются оригинальными и представлены здесь для полноты изложения. Однако найти способ их применения не было тривиальным.
источник
mat[i]
mat[j]
mat
что кажется важным. Я понимаю, как это можно определить, но мне интересно,(mat[i] & mat[j]).count()
будет ли работать как угодно с любым контейнером STL.mat
- я думаю, мы должны использоватьstd::vector<boost::dynamic_bitset<int64_t>>
.mat
: да, я имел в виду стандартный битсет на самом деле, ноboost::dynamic_bitset
в данном случае это даже лучше, потому что его размер не должен быть постоянным во время компиляции. Отредактирую ответ, чтобы добавить эту деталь и уточнить подход четырех россиян.