Как уменьшить временную сложность в этой проблеме

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

И вам нужно найти вхождение этого паттерна
1
11

Итак, глядя на приведенную выше матрицу, очевидно, что ответом является 6 .И я решил это следующим образом:

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);
}

Следующий вопрос - улучшить время.Я не смог ответить точное решение .

Может кто-нибудь помочь мне с этим?Я просто хочу знать это для моего собственного любопытства.

Answer 1

Вот небольшая оптимизация, которая зависит от шаблона ввода.

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);
}

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

Что касается конкретной проблемы, ваше решение подходит.

Есть 2 альтернативных метода, которые будут полезны, если вы хотите найти другие шаблоны в той же матрице или в случае очень больших матриц и больших шаблонов:

https://en.wikipedia.org/wiki/Summed-area_table

https://en.wikipedia.org/wiki/Discrete_Fourier_transform

оба требуют некоторой предварительной обработки исходной матрицы, но затем обеспечат более быструю проверку шаблонов шаблонов. Вы найдете реализации обоих в библиотеке обработки изображений OpenCV.