algorithm - BFS 的空间复杂度

Question

这是 BFS 实现的代码片段-

public static void findShortestReach(LinkedList<Integer>[] adjList,int start,int nodes)
{
    int[] level=new int[nodes];     //keeps track of distance of node in terms of number of edges
    Arrays.fill(level,-1);           //-1 signifies unreachable
    level[start-1]=0;               //distance of start from start is 0
    ArrayList<Integer> frontier=new ArrayList<Integer>();
    frontier.add(start);
    int i=1;
    while(!frontier.isEmpty())          //'nodes' times
    {
        ArrayList<Integer> next=new ArrayList<Integer>();
        for(int j:frontier)
        {   

            for(int k:adjList[j-1])
            {   
                //System.out.println(k+"hi");
                if(level[k-1]==-1)
                {
                    level[k-1]=6*i;
                    next.add(k);
                }

            }
        }
        frontier=next;
        i=i+1;
    }
    for(int l=0;l<nodes;l++)
    {    
        if(level[l]!=0)
        {
            System.out.print(level[l]+" ");


        }

    }



}

其中“start”是起始节点，“nodes”是节点数。上述算法在空间方面效率低下，因为它在 while 循环内一次又一次地创建 ArrayList。我无法在复杂性方面说服自己。

while 循环将运行“节点”次，即 V 次。每一次 ArrayList 都会被创建，它的大小会随着元素的添加而增加。在最坏的情况下，它存储的最大元素数将为 V-1。因此空间复杂度为 V^2。但是，一旦它被填充，它是否会捕获 arraylist 的加倍，因为在 while 循环的每次迭代期间会发生很多次。这种情况下如何准确判断空间复杂度？

Answer 1

如果我对问题的理解正确，那么您的推理是正确的。请注意，复制数据结构的一部分不会增加空间复杂度。在您的情况下，将复制一个邻接列表(最多包含 |V| 个节点)，但这最多发生 O(|V|) 次。总的来说，while 循环中的复制花费了 O(|V|^2) 时间，这是由整体运行时复杂度决定的，也是 O(|V|^2) 。