Как рассчитать сложность этой программы?Может ли быть другое решение с меньшей сложностью? - PullRequest
Новая
       78

Как рассчитать сложность этой программы?Может ли быть другое решение с меньшей сложностью?

0 голосов
/ 03 июня 2019

Вопрос ссылка: https://leetcode.com/contest/biweekly-contest-1/problems/campus-bikes-ii/

Я хочу вычислить сложность этой программы, я думаю, что сложность моего кода равна O (b ^ w), где b - это размер общего велосипеда, а w - размер всего рабочего, хотя я не уверен .

В моей функции "bikeAssign ()", которая в основном работает как dfs, сначала у 1-го работника есть выбор b (всего велосипедов), у 2-го - b-1, поэтому я думаю, что сложность времени будет такой:

(b) (b-1) (b-2) ...... (bw), что почти равно O (b ^ w).

Сложность пространства: O (w) только для dfs (bikeAssign ()) 

public:
    int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        int w = workers.size();
        int b = bikes.size();
        vector<vector<int> > dist;

        //complexity O(w*b)
        for( vector<int> worker : workers ) {
            vector<int> v;
            for( vector<int> bike : bikes ) {
                v.push_back( abs(worker[0]-bike[0]) + abs(worker[1]-bike[1]) );
            }
            dist.push_back(v);
        }

        vector<int> vis(b,0);
        //complexity O(b^w) My calculation
        return bikeAssign(dist, vis, 0, w );
    }


    // COMPLEXITY OF THIS FUNCTION ????

    int bikeAssign( vector<vector<int> > &dist, vector<int> &vis, int cnt, int w ) {
        if( cnt == w )
            return 0;

        int res = INT_MAX;
        for( int i=0;i<dist[0].size();i++ ) {
            if( vis[i] == 0 ) {
                vis[i] = 1;
                res = min( res, dist[cnt][i] + bikeAssign( dist, vis, cnt+1, w) );
                vis[i] = 0;
            }
        }

        return res;
    }
};

Это решение принято, но я запутался в сложности. Может ли кто-нибудь помочь мне выяснить- 1. Сложность этой программы с пояснениями. 2. Дайте мне знать, если есть какое-либо другое решение с большей сложностью.

Буду признателен за любую помощь.

Ответы [ 2 ]

1 голос
/ 03 июня 2019

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

Так что o(b!/(b-w)!) где b = bikes.size()и w = workers.size().Так что этот алгоритм не очень хорошо масштабируется.

Это похоже на проблему, похожую на задачу коммивояжера (но у вас есть несколько «продавцов»).

1 голос
/ 03 июня 2019

СЛОЖНОСТЬ ЭТОЙ ФУНКЦИИ ????

Давайте проанализируем эту сложность - 

for( int i=0;i<dist[0].size();i++ ) {
      if( vis[i] == 0 ) {
            vis[i] = 1;
            res = min( res, dist[cnt][i] + bikeAssign( dist, vis, cnt+1, w) );
            vis[i] = 0;
      }
}

Здесь этот цикл выполняется O(dist[0].size()) раз.Позволяет dSize = dist[0].size();

Так что здесь сложность O(dSize).Но он работает для каждого dSize (как для параметра, который for выполняет цикл один раз для каждого элемента).Таким образом, общая сложность составляет O(dSize*dSize).

А что такое dSize?Хорошо, dSize имеет размер dist [0] .Так вот, сколько элементов помещается в вектор 0-index из dist.Это номера велосипеда.Таким образом, общая сложность этой функции составляет O(b*b).

...