我可以想象你可以为最佳情况优化它,但是我想说你的最坏情况仍然是O(N*N):你的最坏情况将是所有0的数组,你必须检查每个元素。

优化将涉及在您找到“1”时跳过一行或一列(我可以提供详细信息,但您说您不关心O(N*N)”,但除非您有元数据来指示整个行/列为空,或者除非您有一种SIMD样式的方法来一次检查多个字段(例如,如果每行都按4对齐,并且您可以读取)32位的数据,或者如果您的数据是位掩码的形式),您将始终必须处理全零数组的问题。

显然,输出矩阵或其求反的版本也不必是稀疏的(取一个第一行的一半设置为1,其他任何设置为0的矩阵来查看),因此时间取决于允许对输出使用的格式。(我假设输入是一个元素列表或类似的东西,否则你就不能利用矩阵的稀疏性。)

更新: 根据语言的不同,可以使用一些技巧通过多次引用同一行来返回普通的二维数组。例如,在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;

使用2*N的额外存储空间,您可以在O(N*N)中执行操作。只需为每一行创建一个掩码,为每一列创建一个掩码-扫描数组并在运行时更新掩码。然后再次扫描,根据掩模填充结果矩阵。

如果你真的想保留它的话)。所以加载初始矩阵仍然是O(N) N) 但更新可能要少得多。

输入矩阵可能是稀疏的,但除非你能以稀疏格式得到它(例如,一个 (i,j) 初始设置的对),仅读取输入将消耗(n^2)时间。即使使用稀疏输入,也很容易以O(n^2)输出结束。作为欺骗,如果您被允许输出一个集合行和集合列的列表,那么您就可以使用线性时间。当你的算法必须产生比“是”或“否”更重要的结果时,就没有什么魔力了。

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):你不必计算和存储整个矩阵:你只需要两个向量,L和C,每个向量的大小为N:

如果x是一行1,则L[x]为1,否则为0;

您可以用O(N)来构造这些向量,因为初始矩阵是稀疏的;您的输入数据将不是一个矩阵,而是一个包含每个非零元素的坐标(行、列)的列表。在阅读此列表时,将L[line]=1和C[column]=1设置为1,问题就解决了:如果L[L]=1或C[C]=1,则M[L,C]=1

多亏了mb14的评论,我想我可以在不到一个月的时间内解决这个问题 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 

让我们有两个大小为N的数组(这是最坏的情况)。。。一个专用于索引行和其他列。。。 把[i][1]=0的放在一个数组中,然后把[1][j]=0的放在另一个数组中。。

然后只取这些值并检查第二行和第二列…通过这种方式,我们得到只有0的行和第二列的值。。。

行数组中的值数表示结果数组中的0数,[行数组值][列数组值]表示这些点。。。。

N) 最糟糕的是O(N) N) 。。。如我们所见,数组(大小为N)减小了。。。。

我做了一些数组,得到了所有数组的结果。。。:)

如果我错了,请纠正我。。。

很明显,我们有 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) 未设置为1(在5x5的情况下为20)。

O(N^2) 时间:沿顶行和列求和,如果行或列得到非零答案,则填写整行或整列;然后解决较小的(N-1)x(N-1)问题。

所以有些案子至少需要 N^2 任何案件都可以在 N^2个 没有多余的空间。

如果你的矩阵是稀疏的,那么复杂度很大程度上取决于输入编码,尤其是在N中没有很好的度量 ² 或者类似的,但就N而言,你的输入复杂度M ^在里面 和 你的输出复杂性 . 我希望有点像O(N+M) ^{在里面 外面的} )但这在很大程度上取决于编码和使用它的技巧。

这完全取决于您的输入数据结构。如果将矩阵(1和0)作为二维数组传递,则需要遍历它,即O(N^2)。但是由于你的数据是稀疏的,如果你只传递1作为输入,你可以这样做,所以输出是O(M),其中M不是单元格的数目,而是1单元格的数目。类似于以下内容(下面的伪代码):

list f(list l) {
   list rows_1;
   list cols_1;

    for each elem in l {
        rows_1[elem.row] = 1;
        cols_1[elem.col] = 1;
    }

    list result;
    for each row in rows_1 {
        for each col in cols_1 {
             if (row == 1 || col == 1) {
                 add(result, new_elem(row, col));
             }
        }
    } 
   return result;
}

编辑:事实上,这和安迪的一样。

行只有两种可能的情况:

• 所有其他行都是相同的:即当输入中有一个元素(uj)时,第j个元素是1。

因此,结果可以紧凑地表示为对行的引用数组。因为我们只需要两行,所以结果也只会消耗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,1,1,0,0}, {0,0,0,0,0}, {0,0,0,0,0} };

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();

}