Какова временная сложность следующего рекурсивного кода

Не уверен, актуально это или нет, но проблема, которую я пытаюсь решить, -

~~~~~~~~~~~~~ Кратчайшее расстояние от всех зданий ~~~~~~~~~~~~~~~

Вы хотите построить дом на пустом участке земли, который за кратчайшее расстояние достигнет всех построек. Вы можете двигаться только вверх, вниз, влево и вправо. Вам предоставляется двухмерная сетка значений 0, 1 или 2, где:

Каждый 0 обозначает пустую землю, по которой вы можете свободно проходить. Каждая единица обозначает здание, через которое вы не можете пройти. Каждые 2 обозначают препятствие, которое вы не можете преодолеть.

Найдите наименьшее расстояние от пустой земли, на котором можно получить доступ ко всем зданиям ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~

Хотя мое решение работает правильно с небольшими входными данными, оно истекает по тайм-ауту для больших входных данных из-за большой временной сложности.

Однако я не уверен в точной временной сложности этого решения и хочу правильно понять, какова временная сложность этого решения, чтобы я мог попытаться улучшить его, если это возможно.

Я почти уверен, что временная сложность внешнего цикла составляет O (MN) (M - общее количество строк, а N - общее количество столбцов), потому что мы перебираем все позиции сетки, но в чем я не уверен - временная сложность рекурсивного метода shortDist. Это также O (MN), потому что в худшем случае он коснется каждой позиции сетки, и, следовательно, общая временная сложность этого решения будет O (M ^ 2 * N ^ 2) или что-то еще, Если это так, было бы здорово, если бы кто-нибудь мог мне об этом объяснить.

Мое решение

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {

        vector<std::pair<int,int>> dir = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        // pair(row, col) -> distance
        map<std::pair<int,int>, int> cache;
        vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false)); // to check if we have already visited that location on the grid
        int minDist = INT_MAX;
        int maxCount =0;
        // Finding number of 1's
        for(int i =0; i< grid.size(); i++)
        {
            for(int y =0; y < grid[0].size(); y++)
            {
                if(grid[i][y] == 1)
                {
                    maxCount++;
                }
            }
        }
        // For each 0 find the distance of each 1's and their count
        // if the count of 1's is less than the number of 1's in the
        // grid that grid position is not an acceptable pos
        for(int i =0; i< grid.size(); i++)
        {
            for(int y =0; y < grid[0].size(); y++)
            {
                if(grid[i][y] == 0)
                {
                    shortDist(grid, cache, dir, visited, i, y, 0);
                    int dist =0;
                    int count = cache.size();// number of 1's
                    if(count == maxCount)
                    {
                        // if we are here it implies that the empty land space have path to all the buildings
                        for(auto iter = cache.begin(); iter != cache.end(); iter++)
                        {
                            dist += iter->second;
                        }
                        if(dist < minDist)
                        {
                            minDist = dist;
                        }
                    }
                    cache.clear();
                }       
            }
        }

        return minDist == INT_MAX ? -1 : minDist;

    }

    void shortDist(vector<vector<int>>& grid, map<std::pair<int,int>, int>& cache, vector<std::pair<int,int>>& dir, vector<vector<bool>>& visited, int row, int col, int dist)
    {
        if(row < 0 || col < 0 || row >= grid.size() || col >= grid[0].size())
        {
            return;
        }
        if(grid[row][col] == 2)
        {
            return;
        }
        if(grid[row][col] == 1)
        {
            auto found = cache.find(make_pair(row, col));
            if(found == cache.end())
            {
                cache[(make_pair(row, col))] = dist;
            }
            else
            {
                found->second = min(found->second, dist);
            }

            return;
        }

        if(visited[row][col])
        {
            return;
        }

        visited[row][col] = true;
        for(int i =0; i < dir.size(); i++)
        {
            int newRow = row + dir[i].first;
            int newCol = col + dir[i].second;
            shortDist(grid, cache, dir, visited, newRow, newCol, dist+1);
        }
        visited[row][col] = false;
    }
};

Было бы хорошо, если бы люди, которые проголосовали, укажите, что они считают неуместным или неуместным, потому что я действительно чувствую, что это искреннее сомнение, и я четко провел свое исследование и даже предоставил то, что, по моему мнению, могло бы быть ответом с объяснением. По крайней мере, я хотел бы знать, что еще я могу предоставить в следующий раз, чтобы прояснить ситуацию.

bourne 10.09.2018 08:36

Если вы можете пройти только через 0 и вам нужно получить доступ ко всем зданиям, тогда должна быть подключена сеть из 0. Может быть, это сводится к алгоритму Дейкстры, если известны пути.

macroland 10.09.2018 08:55

Я бы посоветовал вам добавить к своему вопросу тег алгоритма.

macroland 10.09.2018 08:56

В основном я начинаю с 0 и иду во всех четырех направлениях, пока не найду 1. Как только я нахожу 1, я сохраняю строку и столбец 1 и расстояние на карте. Поскольку тот же 1 может быть позже обнаружен с меньшим расстоянием, в этом случае я обновляю расстояние. После проверки расстояния для всех единожды, если число найденных 1 совпадает с общим количеством единиц в сетке, я проверяю и обновляю идентификатор расстояния меньше. Хорошо, я также добавлю теги алгоритмов.

bourne 10.09.2018 09:19

Может быть, больше подходит для проверки кода.

sim 10.09.2018 09:54
2
5
243
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Насколько я понимаю, shortDist вносит основной вклад.

Функция shortDist имеет для find O (журнал (MN)), поскольку кеш может содержать максимум записей в строках * столбцах (при использовании std::map использование std::unordered_map равно O (1), если у вас есть идеальная хеш-функция). Затем вы выполняете рекурсию для расстояния, которое составляет D = max (M, N), на самом деле вы посещаете каждые MN точек. в общей сложности O (MN log (MN)) для каждого вызова от shortestDistance.

В shortestDistance второй цикл по сетке имеет O (MN) для первых двух циклов, а затем O (MN) для цикла по кешу, что дает O (M ^ 2 * N ^ 2), вызов shortDist - O (M ^ 2N ^ 2 журнал (MN)).

Вы можете сохранить журнал (MN), если используете другой массив MN для прямого поиска значения.

Оптимизация внедрения.

Ваш вызов shortDist имеет слишком много параметров.

Вектор dir должен быть constexpr std :: array, поскольку он никогда не изменяется и используется во всех поисках.

Cache и visited должны быть членами класса, этот метод shortDistance сбрасывается для каждого вызова, в противном случае экземпляр Solution используется только один раз.

Перетаскивание сетки с вами в качестве параметра также кажется расточительным, учитывая, сколько раз вы это делаете. Сделав его ссылкой или копией класса, можно решить эту проблему.

Тогда shortDist имеет только 3 разумных параметра.

Вы можете сэкономить значительную потерю производительности, сделав сетку одномерной и вычислив индекс самостоятельно, сократив каждый поиск x, y с двух до одного доступа к памяти в shortDist.

Вы правы, если я предполагал, что find равен O (1), но это только в том случае, когда у вас идеальный хеш, и наихудшая временная сложность может быть другой. Один вопрос, хотя вы указали выше, что это O (log (MN)), но если хеш-ведро является связаннымList, худшая временная сложность не будет O (MN), а не O (log (MN)), и нам придется поиск по всему элементу, чтобы найти элемент.

bourne 10.09.2018 20:16

Я предполагаю, что для журнала (MN) используется std :: map, поскольку std :: unordered_map будет наихудшим случаем MN.

Surt 10.09.2018 21:52

Но, как я уже сказал, вы можете заменить карту сеткой того же размера, что и сетка для O (1), которая для всех практических целей была бы идеальной, а именно 1: 1.

Surt 10.09.2018 21:53

Другие вопросы по теме