天真的方式在1和0的矩形中查找最大块
我试图想出bruteforce（天真）解决方案来找到1或0的矩形中的最大块1或0.我知道可以在O(n)时间完成的最佳方式，其中n是总数矩形的大小。
1 1 0 1 0 1
1 0 0 0 1 1
1 0 0 0 1 1
1 1 0 1 1 0
在上面的矩形中，它是从大小为6的（第2行，第2列）开始的矩形。我在想这个..
遍历每个元素，然后通过遍历它的所有方向来查找它的大小。
它是暴力吗？ 什么是复杂性？ 我正在浏览所有n元素，但是我正在遍历所有方向，那会是多少？
我知道这个问题已经被问了100次，但他们讨论的是最佳解决方案。 我在寻找的是一个暴力解决方案及其复杂性？
你描述的算法看起来像这样的C代码：
//for each entry
for(int x = 0; x < width; ++x)
for(int y = 0; y < height; ++y)
{
char lookFor = entries[x][y];
int area = 0;
for(int row = y; row < height; ++row)
{
if(entries[x, row] != lookFor)
break;
for(int col = x; col < width; ++col)
{
if(entries[col, row] != lookFor)
break;
int currentArea = (col - x + 1) * (row - y + 1);
if(currentArea > area)
{
//save the current rect
}
}
}
}
有四个嵌套循环。 外部循环将正好重复n次（其中n是条目数）。 内部循环将平均重复width * f1和height * f2次（其中f1和f2是某个常数分数）。 算法的其余部分需要一定的时间并且不依赖于问题的大小。
因此，复杂度是O(n * f1 * width * f2 * height) = O(n^2) ，这基本上意味着“去每个入口并从那里再次访问每个入口”，而不管所有入口是否真的需要进行检查或只是一个随问题大小增加的不变分数。
编辑
上面的解释假设条目不是随机分布的，对于较大的字段，它更可能找到较大的同质子区域。 如果情况并非如此，并且内部循环的平均迭代次数不取决于字段大小（例如对于随机分布的条目），则所得到的时间复杂度为O(n)
查看“连接组件”算法以获取更多想法。 你所呈现的二进制值的二维数组看起来就像二进制黑白图像。 一个重要的例外是，在图像处理中，我们通常允许连接的组件（一个0或1的斑点）具有非矩形形状。 对现有的多遍和单遍算法进行一些调整应该很容易实现。
http://en.wikipedia.org/wiki/Connected-component_labeling
虽然这是一种比您需要的更一般的解决方案，但您也可以运行连接组件算法来查找所有连接区域（0或1，背景或前景），然后过滤结果组件（又名斑点）。 我还会提到，对于前景组件，最好选择“4连通性”而不是“8连通性”，其中前者意味着连接仅允许位于中心像素的上方，下方，左侧和右侧像素，而后者意味着中心像素周围的八个像素中的任何一个都允许连接。
更远一点，对于非常大的二维数组，它可能（可能）有助于首先通过创建我们称之为“图像金字塔”的方式来缩小搜索空间，这意味着一堆尺寸逐渐缩小的数组：每个1/2尺寸（根据需要填充），1/4，1/8等等。 在降低分辨率的图像中可检测的矩形是在非常大的图像（或二维数组比特）中作为最大矩形的好候选。 虽然这可能不是您考虑的任何情况下的最佳解决方案，但它是可扩展的。 当然，需要花费一些努力来确定缩放阵列/图像的成本与在原始大图像中保持相对较大的候选矩形列表的成本。
游程编码也可以帮助你，特别是因为你正在处理矩形而不是任意形状的连接组件。 运行长度编码将每行表示为延伸或“运行长度”0或1。 这种技术被用来在十年或两年前加速连接组件算法，这仍然是一种合理的方法。
无论如何，这不是对你的问题最直接的回答，但我希望它有所帮助。
蛮力一般分为两个（有时是连续的）部分。 第一部分是为解决问题提供所有可能的候选人。 第二部分是测试他们是否真的是解决方案。
蛮力：假设你的矩形是mx n。 生成大小为axb的所有子矩形，其中a在{1..m}中，b在{1..n}中。 将maximum变量设置为0.测试所有子矩形以查看它是否全部为0和1。 如果是的话，让maximum = max(maximum, size(sub-rectangle)或者简单地从测试更大的子矩形开始，然后移动到测试更小的子矩形。只要找到一个全为0的子矩形或者1s，stop。时间复杂度将是相同的，因为在两种方法的最坏情况下，您仍然需要遍历所有子矩形。
时间复杂度：
我们来计算在每一步生成的子矩形的数量。
有大小为1 x 1的m * n个子矩形。
有（m-1）* n个尺寸为2 x 1的子矩形。
有大小为1 x 2的m *（n-1）个子矩形。
有（m-1）*（n-1）个尺寸为2 x 2的子矩形。
... <等等>
存在大小为m×n的（m-（m-1））*（n-（n-1））个子矩形。
因此，用于计算尺寸为mxn的较大矩形的大小为axb的子矩形数的公式简单地为：
number_of_subrectangles_of_size_a_b = (ma) * (mb)
如果我们将这些数字想象成一个算术系列，我们就可以得到
1*1 + 1*2 + ... + 1*n + 2*1 + ... + m*n
这可以作为因素：
(1 + 2 + ... + m) * (1 + 2 + ... + n) 。
这两个算术级数分别收敛到O（m2）和O（n2）的数量级。 因此生成一个m * n矩形的所有子矩形是O（m2n2）。 现在我们看看测试阶段。
在生成所有子矩形之后，测试每个大小为axb的子矩形是全0还是全1都是O（a * b）。 与之前生成大小为axb的子矩形的步骤不同，后者随着axb的减小而向上缩放，此步骤与ax b的大小成比例地增加。
例如：有一个大小为mx n的子矩形。 但是测试一下，看看矩形是全0还是全1都需要O（m * n）时间。 相反，有大小为1的m * n个子矩形。但是测试以查看这些矩形是全是0还是全1，每个矩形只需要O（1）个时间。
你最终为时间复杂性而结束的是这样一个系列：
O( (m-(m-1))(n-(n-1))*(mn) + (m-(m-1))(n-(n-2))*m(n-1)... + mn*(m-(m-1))(n-(n-1)) )
注意2件事。
（m / 2）（n / 2）（m / 2）（n / 2），即O（m2n2）
该系列中总共有m * n个术语。
因此，蛮力解的测试阶段将为O（mn * m2n2）= O（m3n3）。
总时间复杂度是：
O(generating) + O(testing) = O(m2n2 + m3n3) = O(m3n3)
如果给定矩形的面积是N，那么我们将具有O（N3）时间复杂度。
链接地址: http://www.djcxy.com/p/16923.html上一篇: Naive way to find largest block in a rectangle of 1's and 0's