找到最大的子矩阵满是那些线性时间 [英] find the largest sub- matrix full of ones in linear time

问题描述

由于一个n×n矩阵与零和一，找到最大的子 矩阵充满了那些线性时间。有人告诉我，有一个解决方案 O（n）的时间复杂度存在。如果在一个的N×N N ^ 2元件 矩阵如何线性解决方案存在吗？

Given an n by n matrix with zeros and ones, find the largest sub- matrix full of ones in linear time. I was told that a solution with O(n) time complexity exists. If there are n^2 elements in a n X n matrix how does a linear solution exist?

推荐答案

您不能搜索 n阶矩阵 N 的时间。反例：零的设置为一个单一的元素的矩阵。你必须检查每一个元素来查找，一个是，这样的时间必须至少为O（n ^ 2）。

You can't search a n x n matrix in n time. Counterexample: a matrix of zeros with a single element set to one. You have to check every element to find where that one is, so time must be at least O(n^2).

现在，如果你说的矩阵具有 N = N ^ 2 条目，您只考虑子矩阵的形成一个连续的块，那么你应该能够走斜对面的基质，保持了那些每个矩形的轨道，当您去发现最大的子矩阵。您可以在一般有多达 O（开方（N））矩形活跃的同时，你需要在其中进行搜索以找出哪些矩形是最大的，所以你应该是能够做到这一点的 O（N ^（3/2）*日志（N））的时间。

Now if you say that the matrix has N = n^2 entries, and you only consider submatrices that form a contiguous block, then you should be able to find the largest submatrix by walking diagonally across the matrix, keeping track of every rectangle of ones as you go. You could in general have up to O(sqrt(N)) rectangles active simultaneously, and you would need to search in them to figure out which rectangle was the largest, so you ought to be able to do this in O(N^(3/2) * log(N)) time.

如果你可以选择任意的行和列组成的子矩阵，那么我看不出有什么明显的多项式时间算法。

If you can pick arbitrary rows and columns to form your submatrix, then I don't see any obvious polynomial time algorithm.

这篇关于找到最大的子矩阵满是那些线性时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！