Можем ли мы вычислить это менее чем O (N * N) ... (NLOGN или N)

StackOverflow https://stackoverflow.com/questions/3659506

Вопрос

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

Введите 2D N * N массива 0 и 1 '. Если a (i, j) = 1, то все значения, соответствующие ath rows и 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).

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

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

Это было полезно?

Решение 7

Hii парней,

Благодаря комментарию от MB14 я думаю, что я мог бы получить его решаемым менее чем O (NN) Время ... худшее потребовало бы о (nN) ...

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

  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; полностью ...

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

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

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

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

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

Другие советы

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

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

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

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

Простое решение для пространства o (m + n) и времени (m - количество в входной матрице): возьмите две массивы длины n, заполненные с теми, итерацией через все входные, а для каждой падения X координировать от первого массива и Y от второго. Выход - это две массивы, которые четко определяют матрицу результата: его координата (x, y) составляет 0 iff Координата 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;

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

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

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

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

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

Комментарий McDowella на другой ответ предлагает еще один альтернативный входной формат: кодирование длины пробега. Для разреженного входа, который явно не требует не более, чем (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).

Ты говоришь:

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

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

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

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

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

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

Там явно до 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) Время: сумма вдоль верхнего ряда и дайте столбцу, и если ряд или столбец получает ненулевой ответ, заполните всю строку или столбец; Затем решите проблему меньшего (N-1) X (N-1).

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

Если ваша матрица редкая, сложность многое зависит от входной кодировки и в частности, не хорошо измерено в NN2 или что-то в этом роде, но с точки зрения N ваша входная сложность Mв а также Ваша выходная сложность Mвне. Отказ Я ожидал чего-то вроде o (n + mв + М.вне) Но много в зависимости от кодирования и трюков, которые вы можете играть с ним.

Это полностью зависит от вашей входной структуры данных. Если вы передаете свою матрицу (1s и 0s) в качестве массива 2D, вам нужно пройти его, и это O (n ^ 2). Но поскольку ваши данные редятся, если вы проходите только в качестве ввода, вы можете сделать это, чтобы OUPTUT IS O (M), где M не количество клеток, а количество 1 клетки. Это было бы чем-то похожее на это (псевдокод ниже):

Список f (список l) {Список строк_1; Список Cols_1; Для каждого элемента в L {Rows_1 [Elem.row] = 1; Cols_1 [Elem.Col] = 1; } Результат списка; Для каждой строки в Rows_1 {для каждого Col в Cols_1 {If (row == 1 || col == 1) {add (результат, new_elem (ряд, col)); }}} Возвращаемый результат; }

Не заполняйте центр матрицы при проверке значений. Когда вы проходите через элементы, когда у вас есть 1 Установите соответствующий элемент в первой строке и первом столбце. Затем вернитесь и заполните и поперелись.

Редактировать: На самом деле, это так же, как Энди.

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

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

  • Ряд, который я заполнен 1-х годом, если есть элемент (I, _) на входе
  • Все остальные строки одинаковы: то есть элемент j-й 1 IFF есть элемент (_, 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 - длина ввода.

#include<stdio.h>

включать

INT MAIN () {INT ARR [5] [5] = {{1,0,0,0,0}, {0,1,1,0,0}, {0,0,0,0,0,0} , {1,0,0,1,0}, {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) .. Я думаю, что это невозможно вообще решить эту проблему в < O (n ^ 2).

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top