algorithm - 在 1's and 0' s 的矩形中查找最大块的天真方法

Question

我正在尝试提出蛮力(天真的)解决方案，以在 1 和 0 的矩形中找到最大的 1 或 0 block 。我知道可以在 O(n) 中完成的最佳方法 time 其中 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 的矩形。我在想这个..

Go through each element and then find the size it makes by iterating in all directions from it.

这是暴力破解吗？会有什么复杂性？我正在遍历 n 的所有元素，但随后我在所有方向上迭代，那会是多少？

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

Answer 1

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