如何计算这个程序的复杂度？是否还有其他更简单的解决方案？

Question

问题link：https://leetcode.com/contest/biweekly-contest-1/problems/campus-bikes-ii/

我想计算这个程序的复杂度，我认为我的代码的复杂度是 O(b^w)，其中 b 是自行车总数，w 是工人总数，尽管我是不确定。

在我的 "bikeAssign()" 函数中，它基本上用作 dfs，首先第一个工人有 b（总自行车）个选项可供选择，第二个有 b-1 个选项可供选择，所以我认为时间复杂度就像这个-

(b)(b-1)(b-2)......(b-w) 差不多等于 O(b^w).

Space 复杂度：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.让我知道是否有任何其他更复杂的解决方案。

如有任何帮助，我们将不胜感激。

Answer 1

COMPLEXITY OF THIS FUNCTION ????

让我们分析一下这个复杂度 -

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

这里这个 for 循环运行 O(dist[0].size()) 次。让dSize = dist[0].size();

所以这里的复杂度是 O(dSize)。但它为每个 dSize 运行（从 for 循环为每个元素运行一次的参数开始）。所以这里的整体复杂度是 O(dSize*dSize).

什么是dSize？好吧，dSize就是dist[0]的大小。这就是将多少元素推到 dist 向量的 0-index 中。那是自行车的数量。所以这个函数的整体复杂度是O(b*b)。

Answer 2

由于此算法递归扫描所有可能的 variation without repetition 工人收集的自行车，因此复杂性与此变化数量成正比。

因此 o(b!/(b-w)!) 其中 b = bikes.size() 和 w = workers.size()。所以这个算法不能很好地扩展。

这看起来像一个类似于 traveling salesman problem 的问题（但你有多个 "salesmans"）。

如何计算这个程序的复杂度？是否还有其他更简单的解决方案？

How to calculate complexity of this program? Can there be any other solution with less complexity?

c++

algorithm

time-complexity

space-complexity