我想了解为什么这段代码运行得这么慢

Question

我已经编写了一段代码，也许是一个简单的编码测试。 （详情见下文）

拳击手打比赛

更好的人总是胜利 前任） 如果A拳击手比B更好，A总是赢B 如果 C 拳击手比 A 更好，C 总是赢 A、B

So, always (C > A > B), never (C > A > B > C) things.

比赛结束后，部分比赛结果丢失。 根据您得到的结果，确定有多少拳击手可以最终排名。

*constrains
i)  1 <= boxers <= 100.
ii)  1 <= results.size() <= 4500, results contains match_data.
iii) match_data [A, B] means (A defeated B).
iV) no contradictions in the data: if [A,B] exist, [B,A] does not.

----------------------------------------------------------------------

N of boxer                       results                          answer

    5             [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]      2

-----------------------------------------------------------------------

                        [[  explain  ]]

在这种情况下，你可以构建两个等级链。

4 > 3 > 2 > 5 1 > 2 > 5

这里2、5可以分别确认自己的排名第4、第5 但是，由于缺少数据，4,3,1 无法确认它们的相对排名。

因此，答案是2；

我的代码如下

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

int win = 0;
int lose = 1;

int solution(int n, vector<vector<int>> results) {

    queue<pair<int, int>> q;

    vector<vector<vector<int>>> Graph(n, vector<vector<int>>(2));

    vector<int> rating = vector(n,0);

    vector<vector<vector<int>>> List(n, vector<vector<int>>(2, vector<int>(n, 0)));


    for(int match=0; match < results.size(); match++){

        int winner = results[match][win]-1;
        int loser = results[match][lose]-1;

        Graph[winner][win].push_back(loser);
        Graph[loser][lose].push_back(winner);
    
    }

    for(int index=0; index<n; index++){
    
        if(Graph[index][win].size() == 0 && Graph[index][lose].size() == 0) return 0;
    
        if(Graph[index][win].size() == 0){
            for(int i=0; i<Graph[index][lose].size(); i++){
                q.push({Graph[index][lose][i], index});
            }
            while(!q.empty()){
                auto [winner, loser] = q.front();
                q.pop();
            
                if(List[winner][win][loser]==0){
                    List[winner][win][loser] = 1;
                    rating[winner]++;
                }
            
            
                for(int j=0; j<n; j++){
                    if(List[loser][win][j] == 1 && List[winner][win][j] == 0){
                        List[winner][win][j] = 1;
                        rating[winner]++;
                    }
                }
            
                for(int j=0; j<Graph[winner][lose].size(); j++){
                    q.push({Graph[winner][lose][j], winner});
                }
            }
        }
    
        if(Graph[index][lose].size() == 0){
            for(int i=0; i<Graph[index][win].size(); i++){
                q.push({Graph[index][win][i], index});
            }
         
            while(!q.empty()){
                auto [loser, winner] = q.front();
                q.pop();
                
                if(List[loser][lose][winner]==0){
                    List[loser][lose][winner] = 1;
                    rating[loser]++;
                }
                
            
                for(int j=0; j<n; j++){
                    if(List[winner][lose][j] == 1 && List[loser][lose][j] == 0){
                        List[loser][lose][j] = 1;
                        rating[loser]++;
                    }
                }
            
                for(int j=0; j<Graph[loser][win].size(); j++){
                    q.push({Graph[loser][win][j], loser});
                }
            }
        }
    }

    int answer = 0;
    for(int index=0; index<n; index++){
        //cout << rating[index] << ", ";
        if(rating[index]==n-1){
            answer++;
        }
    }

    return answer;

}

我的代码有效，我预计代码的复杂度为 O(n^2+n⋅m) << n = boxer number, m = results.size() >>

当给定大量数据时，它仍然有效，但需要很长时间。

我发现 Floyd-Warshall 算法效果更好。

即便如此，我真的很想知道为什么我的代码花了这么多时间以及它的实际时间复杂度是多少。

1. 感谢您花时间阅读和帮助。

Answer 1

首先，使用您拥有的不同链创建一个森林图，对于每个链，将链的地址存储在一个映射中，其键是节点索引，值是 int 向量的向量，因此是排名向量链。这就是构建过程，最终您将获得

map<int, vector<vector<int>>>

。检查

map

的按键数量。如果键少于

n

，则没有拳击手完全排名。

否则，循环

Map

并在每次迭代中创建一个

set

，用给定节点初始化并循环

vector<vector<int>>

链和内部的每个链，以查看项目是否已在集合中并添加每个元素不在集合中的集合中，直到集合有

n

元素（在这种情况下，节点已完全排名），或者达到搜索结束，在这种情况下，您检查

set

是否有

n

元素，在这种情况下，该节点已完全排名，否则该节点未完全排名。

你的缓慢是因为你

• 循环

  index

  从0到

  n

  • 建立一个胜利/失败的队列
  • 循环队列
    • 循环

      j

      从 0 到

      n

    • 再次循环队列

因此，取而代之的是，从只输了的人（或只赢了，方向由你决定）开始进行完整的图遍历，并构建不同的链和地图。我认为这会让你的算法更加高效。