Можем ли мы вычислить это менее чем за O (n * n) ... (nlogn или n)

Question

Это вопрос, заданный мне очень и очень известным MNC. Вопрос в следующем ...

Введите двумерный массив N * N, состоящий из 0 и 1. Если A (i, j) = 1, то все значения, соответствующие i-й строке и j-му столбцу, будут равны 1. Если уже есть 1, он остается равным 1.

В качестве примера, если у нас есть массив

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

мы должны получить вывод как

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

Входная матрица заполнена редко.

Возможно ли это менее чем за O (N ^ 2)?

Дополнительного места не было, было другое условие. Я хотел бы знать, если есть способ достичь сложности, используя пробел <= O (N). </p>

P.S .: Мне не нужны ответы, которые дают мне сложность O (N * N). Это не домашняя проблема. Я много пытался и не смог найти правильного решения, и подумал, что смогу найти здесь некоторые идеи. Оставьте печать в стороне для сложности

Моя грубая идея состояла в том, чтобы, возможно, динамически исключить количество пройденных элементов, ограничив их до 2N или около того. Но я не мог получить правильное представление.

Answer 1

В худшем случае вам может потребоваться переключить N * N - N битов от 0 до 1, чтобы сгенерировать вывод.Казалось бы, вы довольно хорошо застряли с O (N * N).

Answer 2

Понятно, что ни выходная матрица, ни ее отрицательная версия не должны быть разреженными (возьмите матрицу, для которой половина первой строки установлена ​​в 1, а все остальное в 0 для просмотра), поэтому время зависит от того, какой формат вам разрешено использовать для выхода. (Я предполагаю, что входные данные являются списком элементов или чем-то эквивалентным, так как в противном случае вы не могли бы использовать преимущества разреженной матрицы.)

Простое решение для O (M + N) пространства и времени (M - это число единиц во входной матрице): взять два массива длины N, заполненных единицами, перебрать все входные данные и для каждого удалить координату X из первого массива и Y из второго. Выходными данными являются два массива, которые четко определяют матрицу результата: ее координата (X, Y) равна 0, если координата X первого массива и координата Y второго равны 0.

Обновление: В зависимости от языка, вы можете использовать некоторые хитрости для возврата нормального 2D-массива, ссылаясь на одну и ту же строку несколько раз. Например в PHP:

// compute N-length arrays $X and $Y which have 1 at the column 
// and row positions which had no 1's in the input matrix
// this is O(M+N)
$result = array();
$row_one = array_fill(0,N,1);
for ($i=0; $i<N; $i++) {
    if ($Y[$i]) {
         $result[$i] = &$row_one;
    } else {
         $result[$i] = &$X;
    }
}
return $result;

Конечно, это обычный массив, только если вы не пытаетесь его записать.

Answer 3

Я полагаю, что вы можете оптимизировать его для лучшего случая, но мне хочется сказать, что ваш худший случай все еще O (N * N): ваш худший случай будет массив всех 0, и вы будете должны изучить каждый элемент.

Оптимизация будет включать в себя пропуск строки или столбца, как только вы найдете «1» (я могу сообщить подробности, но вы сказали, что вас не волнует O (N * N) », но если у вас нет метаданных для указать, что вся строка / столбец пуста, или если у вас нет способа SIMD-стиля для проверки нескольких полей одновременно (скажем, если каждая строка выровнена по 4, и вы можете прочитать 32-битные данные или если ваши данные в виде битовой маски), вам всегда придется сталкиваться с проблемой массива со всеми нулями.

Answer 4

Матрица ввода может быть разреженной, но если вы не можете получить ее в разреженном формате (т. Е. Список пар (i,j), которые изначально установлены), простое чтение вашего ввода потребует Ω (n ^ 2) времени.Даже при разреженном вводе легко получить O (n ^ 2) вывод для записи.Как читерство, если вам было разрешено вывести список заданных строк и заданных столбцов, то вы можете перейти к линейному времени.Нет никакого волшебства, когда ваш алгоритм действительно должен давать более существенный результат, чем «да» или «нет».

Комментарий Макдауэллы к другому ответу предлагает другой альтернативный формат ввода: кодирование по длине прогона.Для разреженного ввода, который явно требует не более O (n) времени для его чтения (рассмотрим, сколько переходов между 0 и 1).Однако оттуда это ломается.Рассмотрим входную матрицу, структурированную следующим образом:

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 . . . 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . . .
.     .
.       .
.         .

То есть, чередуя 0 и 1 в первой строке, 0 везде в другом месте.Явно редкий, так как в общей сложности n/2.Однако вывод RLE должен повторять этот шаблон в каждой строке, что приводит к выводу O (n ^ 2).

Answer 5

Так как каждая запись матрицы должна проверяться, ваш худший случай всегда будет N * N.

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

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

Answer 6

Hii, ребята,

благодаря комментарию от mb14, я думаю, что смогу решить эту проблему менее чем за O (N N) времени ... Худшее бы заняло O (N )N) ...

На самом деле, у нас есть данный массив, предположим,

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

Позволяет иметь 2 массива размера N (это будет наихудший случай) ... Один предназначен дляиндексирование строк и других столбцов ... Поместите те, у которых [i] [1] = 0 в одном массиве, а затем [1] [j] = 0 в другом.

Затем возьмите только эти значения ипроверить вторую строку и столбцы ... Таким образом, мы получаем значения строк и столбцов, где есть только 0; 's целиком ...

Число значений в массиве строк дает число0 в массиве результатов и точки [значения массива строки] [значение массива столбца] дают вам эти точки ....

Мы могли бы решить это ниже O (N N) ихудшее - это O (N N) ... Как мы видим, массивы (размера N) уменьшаются ....

Я сделал это для нескольких массивов и получил результат для всехих ...:)

Пожалуйста, поправьте меня, если я где-то ошибаюсь ...

Спасибо за все ваши комментарии, ребята ... Вы все очень полезны, и я узнал немало вещей по пути ...:)

Answer 7

Вы говорите:

мы должны получить вывод как ...

Так что вам нужно вывести всю матрицу, которая имеет N ^ 2 элементов. Это O (N * N).

Сама проблема не в O (N * N): вам не нужно вычислять и хранить всю матрицу: вам нужны только два вектора, L и C, каждый размером N:

L [x] равно 1, если строка x является строкой единиц, в противном случае 0;

C [x] равно 1, если строка x является строкой единиц, в противном случае 0;

Вы можете построить эти векторы в O (N), потому что исходная матрица разрежена; Ваши входные данные будут не матрицей, а списком, содержащим координаты (строка, столбец) каждого ненулевого элемента. При чтении этого списка вы устанавливаете L [line] = 1 и C [column] = 1, и проблема решается: M [l, c] == 1, если L [l] == 1 OR C [c] = = 1

Answer 8

Очевидно, что есть до O(N^2) работы.В матрице

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

все биты должны быть установлены в 1, а N*(N-1) не установлены в единицу (20, в этом случае 5x5).

И наоборот, вы можете прийтис алгоритмом, который всегда делает это за O(N^2) время: сумма по верхней строке и столбцу let, и если строка или столбец получает ненулевой ответ, заполните всю строку или столбец;затем решите меньшую (N-1) x (N-1) задачу.

Таким образом, существуют случаи, которые должны занимать не менее N^2, и любой случай может быть решен в N^2 без лишних пробелов.

Answer 9

#include<stdio.h>

включают

int main () { int arr [5] [5] = {{1,0,0,0,0}, {0,1,1,0,0}, {0,0,0,0,0}, {1,0,0,1,0}, {0,0,0,0,0}}; int var1 = 0, var2 = 0, i, j;

for(i=0;i<5;i++)
   var1 = var1 | arr[0][i];

for(i=0;i<5;i++)
   var2 = var2 | arr[i][0];

for(i=1;i<5;i++)
   for(j=1;j<5;j++)
      if(arr[i][j])
         arr[i][0] = arr[0][j] = 1;

for(i=1;i<5;i++)
   for(j=1;j<5;j++)
          arr[i][j] = arr[i][0] | arr[0][j];

for(i=0;i<5;i++)
   arr[0][i] = var1;

for(i=0;i<5;i++)
   arr[i][0] = var2;

for(i=0;i<5;i++)
{
   printf("\n");             
   for(j=0;j<5;j++)
      printf("%d ",arr[i][j]);
}

getch();

}

Эта программа использует только 2 4 временных переменных (var1, var2, i и j) и, следовательно, работает в постоянном пространстве со сложностью времени O (n ^ 2). Я думаю, что это вообще невозможно решить проблема в

Answer 10

Это зависит от вашей структуры данных.

Есть только два возможных случая для строк:

• Строка i заполняется единицами, если есть элемент (i, _) на входе
• Все остальные строки одинаковы: то есть j-й элемент равен 1, если на входе есть элемент (_, j).

Следовательно,Результат может быть представлен компактно как массив ссылок на строки.Поскольку нам нужны только две строки, результат также будет занимать только O (N) памяти.В качестве примера это может быть реализовано в Python следующим образом:

def f(element_list, N):
  A = [1]*N
  B = [0]*N
  M = [B]*N
  for row, col in element_list:
    M[row] = A
    B[col] = 1
  return M

Пример вызова будет

 f([(1,1),(2,2),(4,3)],5)

с результатом

[[0, 1, 1, 1, 0], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [0, 1, 1, 1, 0], [1, 1, 1, 1, 1]]

Важный моментзаключается в том, что массивы здесь не копируются, т. е. M [row] = A является просто назначением ссылки.Следовательно, сложность O (N + M), где M - длина входа.