请求帮忙分析Java代码的时间与空间复杂度，重点关注集合操作

以下是针对给定Java代码的复杂度分析，重点聚焦集合的添加、更新及复制操作：

class Solution {
   public List<List<Integer>> getAncestors(int n, int[][] edges) {

        Set<Integer> [] ancestors = new Set[n] ;
        int [] in_degree = new int[n] ;
        List<Integer>[] li = new List[n] ;

        for (int i = 0; i < n; i++) {           
            ancestors[i] = new HashSet<> ();
            li[i] = new ArrayList<>() ;
        }
        // 创建邻接表
        for(int []edge : edges){            
            li[edge[0]].add(edge[1]) ;
            in_degree[edge[1]] ++ ;
        }

        helper(n , li , in_degree  , ancestors) ;

        // 将集合转换为有序列表
        List<List<Integer>> lineage = new ArrayList<>() ;
        for (int i = 0; i < n; i++) {
            List<Integer> list = new ArrayList<>() ;
            for(int j : ancestors[i]){
                list.add(j) ;       // 复制集合元素到列表
            }
            Collections.sort(list);
            lineage.add(list) ;
        }
        return lineage ;
    }

    private void helper(int n, List<Integer>[]li, int [] in_degree , Set<Integer> [] ancestors) {
        Queue<Integer> q = new LinkedList<>() ;

        for (int i = 0; i < n; i++)  if(in_degree[i] == 0) q.add(i) ;       

        while(!q.isEmpty()){
            int node = q.remove() ;
            Set<Integer> grand_ancestors = ancestors[node] ;
            for(int u : li[node]){
                ancestors[u].add(node) ;
                ancestors[u].addAll(grand_ancestors) ;
                if(--in_degree[u] == 0) q.add(u) ;
            }
        }
    }
}

一、时间复杂度分析 #

1. 初始化阶段 #

• 初始化ancestors和li数组：遍历n个节点，每个节点创建HashSet和ArrayList，时间复杂度O(n)。
• 构建邻接表：遍历所有E条边，每条边执行两次O(1)操作，时间复杂度O(E)。

2. 拓扑排序遍历（helper方法） #

这是复杂度核心，重点看集合操作：

• 初始化队列：遍历n个节点筛选入度为0的节点，时间O(n)。
• 拓扑循环：每个节点仅出队一次，共n次出队操作：
  • 对每个出队节点的邻接节点u：
    • ancestors[u].add(node)：HashSet的add操作平均O(1)，每个节点只会被添加到后代集合一次，总操作次数等于边数E，总时间O(E)。
    • ancestors[u].addAll(grand_ancestors)：将当前节点的祖先集合批量添加到后代集合，时间取决于源集合大小。全局来看，每个祖先节点只会被添加到所有后代集合一次，最坏情况（如链式图：0→1→2→…→n-1）下，总操作次数为0+1+2+…+(n-1)=O(n²)。

3. 结果转换阶段 #

• 集合转列表：遍历所有节点的祖先集合，总时间等于所有集合的元素总数，最坏O(n²)。
• 列表排序：每个列表排序时间为O(m log m)（m为该节点祖先数量），最坏总时间O(n² log n)。

总时间复杂度 #

最坏情况下为O(n² log n)；若图为稀疏DAG且祖先数量少，时间复杂度接近O(n + E)。

二、空间复杂度分析 #

1. 数据结构占用 #

• ancestors数组：每个元素是存储祖先的HashSet，最坏情况下总元素数为O(n²)，空间O(n²)。
• 邻接表li：存储E条边，空间O(E)。
• 入度数组in_degree：大小为n，空间O(n)。
• 拓扑队列q：最多存储n个节点，空间O(n)。
• 结果列表lineage：存储所有有序祖先列表，总元素数最坏为O(n²)，空间O(n²)。

总空间复杂度 #

最坏情况下为O(n²)，主要由祖先集合和结果列表的存储占用决定。

重点集合操作分析 #

• 添加操作（add）：HashSet平均O(1)，总操作次数等于边数E，总时间O(E)。
• 更新操作（addAll）：批量添加集合元素，总操作次数等于所有节点的祖先数量之和，最坏O(n²)。
• 复制操作（集合转列表）：遍历集合元素并复制，总时间等于所有集合的元素总数，最坏O(n²)。

内容的提问来源于stack exchange，提问作者Sarvagya Porwal