如何减少这个问题的时间复杂度

Question

我最近在一次采访中被问到这个问题，我想知道如何回答这个问题。

您有任何随机顺序的二进制数字二维矩阵 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 0 1 1 0 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 1 1 0 0

你需要找到这种模式的出现 qazxsw poi qazxsw poi

因此，看看上面的矩阵，很明显答案是6.我就这样解决了

1

接下来的问题是为了获得更好的时间复杂性。我无法回答确切的解决方案。

有人可以帮我弄这个吗？我只是想知道这是为了我自己的好奇心。

Answer 1

这是一个小的优化，它取决于输入模式。

11

Answer 2

您的操作的时间复杂度可以描述为O（n），其中n是数组中的点数。您的操作等同于在未排序的数组中搜索某些内容。有些方法可以使您的算法更有效，但是您不能在小于线性时间O（n）内执行此类搜索。

对于某些问题，您可以通过首先排序或收集有关问题的其他信息来提高时间复杂度。对于此问题，您可以证明您的解决方案与阵列的大小线性相关。使用随机数组，3个元素中的每一个都有50％的可能性发生。对于每个n，模式发生的几率为0.5 ^ 3 = 1/8。这意味着您将计算约1/8 * n次出现的模式。单独计数模式需要O（n）时间。

如果您的目标是估计随机数组中出现的次数，则可以在O（1）时间内进行估计。该模式应在随机阵列中发生约1/8 *（j-1）*（i-1）次。

Answer 3

至于具体问题，您的解决方案是合适的。

如果您想在同一矩阵中找到其他模式，或者在非常大的矩阵和更大的模式的情况下，有两种替代方法是有益的：

unsigned int Findpairs(const std::vector<std::vector<unsigned int>>& A) {
    unsigned int count = 0;

    for (unsigned int i = 0; i < (A.size()-1); i++) {
        for (unsigned int j = 0; j < (A[i].size()-1); j++){
            if(A[i][j]==1 && A[i+1][j]==1 && A[i+1][j+1]==1){
                count++;
            }
        }
    }

    return (count);
}

unsigned int Findpairs(const std::vector<std::vector<unsigned int>>& A) {
    unsigned int count = 0;

    for (unsigned int i = 0; i < (A.size() - 1); i++) {
        for (unsigned int j = 0; j < (A[i].size() - 1); j++) {
            if (A[i + 1][j + 1] == 1) {
                if (A[i + 1][j] == 1 && A[i][j] == 1) {
                    count++;
                }
            }
            else {
                j++; //skip a column because our bottom right saw 0
            }
        }
    }

    return (count);
}

两者都需要对原始矩阵进行一些预处理，但随后会为模式模板提供更快的检查。您将在OpenCV图像处理库中找到两者的实现。