该算法的复杂性是什么？ （BFS，最短）

Question

该算法的复杂性是什么？我想表达Big-O的复杂性。 我一生不知道。

问题： REQ_SKILL：所需技能的列表 人：人的人[i]包含该人拥有的技能列表。 考虑一个足够的团队：一组人，对于REQ_SKILLS的每项必需技能，团队中至少有一个人拥有该技能。

示例1：输入：req_skills = [“ java”，“ nodejs”，“ reactjs”]，people = [[“ java”]，[nodejs']，[“ nodejs”，“ nodejs”，“ reactjs”]]输出：[0 ，2]

解决方案：

---

类解决方案：

 def smallestSufficientTeam(self, skills: List[str], people: List[List[str]]) -> List[int]:
    
    # Contains a set with each person containing the skill in the skill
    skill_list: List[Set[str]] = [set() for _ in skills]
        
    # Map w/ skill to index (to fill skill_list easier)
    skill_map: Dict[str, int] = {skill: i for i, skill in enumerate(skills)}
    
    # Fills skill_list with index of skill containing person having skill
    for i, person in enumerate(people):
        for skill in person:
            skill_list[skill_map[skill]].add(i)
    
    # Queue for bfs. Passing in skill_list and current chosen people
    queue: List[Tuple[List[Set[str]], List[int]]] = []
    queue.append((skill_list, []))
    
    while queue != []:
        top_skill_set, top_people = queue.pop(0)
        
        # Picks skill w/ smallest number of people involved, and 
        for person in list(min(top_skill_set, key=len)):
            # Eliminates all skills that "person" has
            new_skill_list = [skill for skill in top_skill_set 
                              if person not in skill]
            
            if new_skill_list == []:
                # If no more skills left, this is shortest group yet
                # Note: Because this is a BFS, this will always be shortest
                return top_people + [person]
            else:
                # Add new_skill_list to queue
                queue.append((new_skill_list, top_people + [person]))
                
    return []  # If no solution exists, return empty array

问题：

非常感谢。

Answer 1

因为您正在做BFS。实际运行时间为O（v + e），其中V为顶点，E是边缘，因为每个都计数一次。

但是，根据E（在这种情况下可能是技能），最佳案例是O（1），最坏的是O（v^2） - bfs是二进制树，因此最大两个连接 。

看看这些来源（它们更详细）：

https：// https：///en.wikipedia.org /wiki/time_complexity

​
.org/breadth-first-search-or-bfs-for-a-graph/?ref=lbp