7

我正在尝试提出蛮力（天真）解决方案，以在 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

在上面的矩形中，它是从 (Row 2, Col 2) 开始的大小为 6 的矩形。我在想这个..

遍历每个元素，然后通过从它的各个方向迭代来找到它的大小。

是蛮力吗？复杂度会是多少？我正在遍历所有为 n 的元素，但随后我在各个方向进行迭代，那会是多少？

我知道这个问题已经被问了 100 次，但他们谈论的是最佳解决方案。我正在寻找的是蛮力解决方案及其复杂性？

4

3 回答 3

3

你描述的算法看起来有点像这个 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)

于 2013-10-26T18:21:15.817 回答
1

蛮力通常分为两个（有时是连续的）部分。第一部分是为问题的解决方案生成所有可能的候选者。第二部分是测试它们，看看它们是否真的是解决方案。

蛮力：假设你的矩形是 mx n。生成所有大小为 axb 的子矩形，其中 a 在 {1..m} 中，b 在 {1..n} 中。将maximum变量设置为 0。测试所有子矩形，看是否全为 0 和 1。如果是，让maximum = max(maximum, size(sub-rectangle). 或者，简单地从测试较大的子矩形开始，然后转向测试较小的子矩形。一旦你找到一个全为 0 或 1 的子矩形，就停止。时间复杂度将是相同的，因为在这两种方法的最坏情况下，您仍然必须遍历所有子矩形。

时间复杂度：

让我们计算一下每一步生成的子矩形的数量。

有 m*n 个大小为 1 x 1 的子矩形。

有 (m-1)*n 个大小为 2 x 1 的子矩形。

有 m*(n-1) 个大小为 1 x 2 的子矩形。

有 (m-1)*(n-1) 个大小为 2 x 2 的子矩形。

... <等等>

有 (m-(m-1))*(n-(n-1)) 个大小为 mx n 的子矩形。

因此，从大小为 mxn 的较大矩形计算大小为 axb 的子矩形的数量的公式很简单：

number_of_subrectangles_of_size_a_b = (m-a) * (m-b)

如果我们想象这些数字以算术级数排列，我们会得到

1*1 + 1*2 + ... + 1*n + 2*1 + ... + m*n

这可以被考虑为：

(1 + 2 + ... + m) * (1 + 2 + ... + n).

这两个算术级数分别收敛到 O(m 2 ) 和 O(n 2 ) 的数量级。因此生成 m*n 矩形的所有子矩形是 O(m 2 n 2 )。现在我们来看测试阶段。

生成所有子矩形后，测试每个大小为 axb 的子矩形是全 0 还是全 1 为 O(a * b)。与上一步生成大小为 axb 的子矩形（随着 axb 减小而向上缩放）不同，此步骤与 axb 的大小成比例地增加。

例如：有 1 个大小为 mx n 的子矩形。但是测试该矩形是全 0 还是全 1 需要 O(m*n) 时间。相反，有 m*n 个大小为 1 的子矩形。但是测试这些矩形是全 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)) )

注意这里的两件事。

  1. 该系列中最大的项将接近 (m / 2)(n / 2)(m / 2) (n / 2) ，即 O(m 2 n 2 )

  2. 该系列共有 m * n 项。

因此，蛮力解决方案的测试阶段将是 O(mn * m 2 n 2 ) = O(m 3 n 3 )。

总时间复杂度为：

O(generating) + O(testing) = O(m2n2 + m3n3) = O(m3n3)

如果给定矩形的面积是 N，我们将有 O(N 3 ) 时间复杂度。

于 2013-10-26T18:55:17.540 回答
0

查看“连接组件”算法以获取更多想法。您作为二进制值的二维数组呈现的内容看起来就像二进制黑白图像。一个重要的例外是，在图像处理中，我们通常允许连接的组件（0 或 1 的 blob）具有非矩形形状。对现有的多通道和单通道算法的一些调整应该很容易实现。

http://en.wikipedia.org/wiki/Connected-component_labeling

尽管它是比您需要的更通用的解决方案，但您也可以运行连接组件算法来查找所有连接区域（0 或 1、背景或前景），然后过滤生成的组件（又名 blob）。我还要提到，对于前景组件，最好选择“4-connectivity”而不是“8-connectivity”，前者意味着只允许在中心像素上方、下方、左侧和右侧的像素处进行连接，后者意味着中心像素周围的八个像素中的任何一个都允许连接。

再远一点，对于非常大的 2D 数组，它可能（只是可能）通过创建我们所谓的“图像金字塔”来帮助首先减少搜索空间，这意味着一堆尺寸逐渐变小的数组：每个 1/2尺寸（根据需要填充）、1/4、1/8 等。在分辨率降低的图像中可检测到的矩形是非常大的图像（或二维位阵列）中最大矩形的良好候选者。尽管对于您正在考虑的任何情况，这可能不是最佳解决方案，但它是可扩展的。自然地，需要一些努力来确定缩放阵列/图像的成本与在原始大图像中维护相对较大的候选矩形列表的成本。

游程编码也可能对您有所帮助，特别是因为您正在处理矩形而不是任意形状的连接组件。游程编码会将每一行表示为 0 或 1 的延伸或“游程长度”。这种技术在一两年前被用于加速连接组件算法，它仍然是一种合理的方法。

无论如何，这不是您问题的最直接答案，但我希望它有所帮助。

于 2013-10-26T18:57:11.830 回答