java - 如何详细计算这段代码的时间复杂度大O？

Question

我试图分析这段代码的时间复杂度，但我被卡住了。我是否认为它是 O(n^2) 时间复杂度，因为有两个 for 循环，或者它只是 O(n) 因为第二个 for 循环并不总是运行？ 使用此代码，我必须根据图形扫描二维数组

//adj is edgeMatrix
public int[] getClosenessCentrality(int[][] adj){
    int size = adj.length * adj.length;
    int[] closeness = new int[size];
    for (int vertex = 0; vertex < adj.length; vertex++) {
        boolean[] visited = new boolean[size];
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(size);


        pq.add(vertex);


        while (!pq.isEmpty()) {
            int u = pq.remove();
            if(!visited[u]) {
                visited[u] = true;
                for (int i = 0; i < size; i++) {
                    //Priority Queue speeds up extract-min
                    if (!visited[i]) {
                        if (adj[u][i] > 0) {
                            pq.add(adj[u][i]+1);
                        } 

                    }
                }
                closeness[vertex] += 1;
            }

        }
    }

    return closeness;
}

Answer 1

如果 n = adj.length 复杂度为 O(n^3 log(n))。

这就是原因。

1. 对于 n 个不同的 vertex 值，我们:
2. 对于所有 n^2 可能的边，我们:
3. 加入优先队列，从优先队列中移除。 (都是 O(log(n^2)) = O(2 log(n)) = O(log(n)) 操作。)

所以把它们放在一起，对于 O(n^ 3 log(n)) 总计。