Эффективный способ найти все нули в матрице?

Question

Я думаю об эффективном алгоритме, позволяющем найти число нулей в строке матрицы, но могу думать только о решении O (n ² ) (т.е. путем итерации по каждой строке и столбцу). Есть ли более эффективный способ подсчета нулей?

Например, с учетом матрицы

3,  4,  5,  6
7,  8,  0,  9
10, 11, 12, 3
4,  0,  9,  10 

Я бы сообщил, что есть два нуля.

Answer 1

Без сохранения какой-либо внешней информации, нет, вы не можете сделать лучше, чем Θ (N ² ).Обоснование простое - если вы не смотрите на все N ² местоположений в матрице, то вы не можете гарантировать, что вы нашли все нули и могли в конечном итоге дать неправильный ответ,Например, если я знаю, что вы просматриваете меньше N ² местоположений, то я могу запустить ваш алгоритм на матрице и посмотреть, сколько нулей вы сообщаете.Затем я мог бы посмотреть на места, к которым у вас не было доступа, заменить их все нулями и снова запустить ваш алгоритм.Поскольку ваш алгоритм не смотрит на эти местоположения, он не может знать, что в них есть нули, и поэтому по крайней мере один из двух прогонов алгоритма вернет неправильный ответ.

В более общем смыслеПри разработке алгоритмов для обработки данных хорошим способом проверить, сможете ли вы добиться большего успеха, чем некоторые среды выполнения, является использование такого рода «состязательного анализа».Задайте себе вопрос: если я бегу быстрее, чем некоторое время O (f (n)), может ли злоумышленник манипулировать данными таким образом, чтобы изменить ответ, но я не смог бы обнаружить?Это тот анализ, который, наряду с более умной математикой, доказывает, что алгоритмы сортировки, основанные на сравнении, не могут работать лучше, чем Ω (n log n) в среднем случае.

Если матрица имеет какую-то другуюсвойства к нему (например, если он отсортирован), то вы могли бы сделать лучше, чем работать в O (N ² ).В качестве примера предположим, что вы знаете, что все строки матрицы отсортированы.Затем вы можете легко выполнить двоичный поиск по каждой строке, чтобы определить, сколько нулей в ней содержится, что занимает O (N log N) времени и быстрее.

В зависимости от параметров вашей настройки, вы можетечтобы алгоритм работал быстрее, если вы предполагаете, что вам разрешено сканировать параллельно.Например, если на вашей машине установлено K процессоров, которые могут быть выделены для задачи сканирования матрицы, то вы можете разбить матрицу на K групп примерно одинакового размера, чтобы каждый процессор подсчитал количество нулей в группе, а затемПодвести итоги этих расчетов.В результате вы получаете время выполнения Θ (N ² / K), поскольку время выполнения разделено на несколько ядер.

Answer 2

Всегда O (n ^ 2) - точнее O (nxm).Вы не можете перепрыгнуть через него.

Но если вы знаете, что матрица разреженная (только несколько элементов имеют ненулевые значения), вы можете хранить только те значения, которые не являютсяноль и размер матрицы.Затем рассмотрите возможность использования хеширования для хранения всей матрицы - обычно создайте хеш, который отображает номер строки во вложенный хеш.

Пример:

m = 
[ 
  0 0 0 0
  0 2 0 0
  0 0 1 0
  0 0 1 0
]

Будет представлен как:

row_numbers = 4
column_numbers = 4
hash = { 1 => { 1 => 2}, 2 => {2 => 1, 3 => 2}}

Тогда:

number_of_zeros = row_numbers * column_numbers - number_of_cells_in_hash(hash)

Answer 3

Для любой несортированной матрицы это должно быть O (n).Так как обычно мы представляем все элементы с 'n'.

Если матрица содержит X строк и столбцов Y, X по Y = n.

Например, в 4 X 4 несортированной матрице это всего элементов 16т. е. когда мы выполняем линейную итерацию с 2 циклами, 4 X 4 = 16 раз.это будет O (n), потому что общее количество элементов в массиве равно 16.

Многие люди проголосовали за O (n ^ 2), потому что они рассматривали n X n как матрицу.

Пожалуйста, исправьтеменя, если мое понимание неверно.

Answer 4

при условии, что данная матрица M выполняет M+(-M) операцию , но использует по умолчанию + вместо my_add(int a, int b), так что

int my_add(int a, int b){
  return (a == b == 0) ? 1 : (a+b);      
}

Это дастВы матрица, как

0  0  0  0
0  0  1  0
0  0  0  0
0  1  0  0

Теперь вы создаете s := 0 и продолжаете добавлять все элементы в s.s += a[i][j]

Вы можете сделать и то и другое за один цикл.s += my_add(a[i][j], (-1)*a[i][j])

Но все же Его O(m*n)

ПРИМЕЧАНИЕ

Чтобы подсчитать число единиц, вы обычно проверяете все элементы в Матрице.не работая со всеми элементами, я не думаю, что вы можете определить количество единиц.и зациклить все элементы его (m*n).Это может быть быстрее, чем (m*n), если и только если вы можете оставить некоторые элементы без контроля и сказать число 1

РЕДАКТИРОВАТЬ

Однако, если вы переместите 2x2 ядро ​​над матрицей и надеюсь, что вы получите (m*n)/k итерацию, например, если вы работаете с соседними элементами * с 1037 * до i < m & i< n

Answer 5

Это не идеальный ответ по причинам, которые я объясню, но он предлагает альтернативное решение, потенциально более быстрое, чем то, которое вы описали:

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

2. После этого выполнить быструю сортировку вэлементы, это может обеспечить производительность O (n log n), в зависимости от случайности матрицы, которую вы вводите.

3. Наконец, подсчет нулевых элементов в начале массива до достижения ненулевого числа.

В некоторых случаях это будет быстрее, чем проверка каждого элемента, хотя в худшем случае быстрая сортировкабудет принимать O (n2), что в дополнение к нулю в конце может быть хуже, чем итерации по каждой строке и столбцу.

Answer 6

Предполагая, что когда вы говорите "в строке матрицы", вы имеете в виду, что у вас есть индекс строки i и вы хотите посчитать количество нулей в i -ой строке, вы можете добиться большего чем O (N ^ 2).

Предположим, N - это количество строк, а M - это количество столбцов, затем сохраните матрица в виде одного массива [3,4,5,6,7,8,0,9,10,11,12,34,0,9,10], затем для доступа к строке i вы получите доступ к массиву по индексу N*i.

Поскольку массивы имеют постоянный доступ по времени, эта часть не зависит от размера матрицы. Затем вы можете выполнить итерацию по всей строке, посетив элемент N*i + j для j от 0 до N-1, это O (N), при условии, что вы знаете, какую строку вы хотите посетить, и используете массив .