Как рассчитать сложность времени Big O этого кода в деталях? - PullRequest
Новая
       7

Как рассчитать сложность времени Big O этого кода в деталях?

0 голосов
/ 14 мая 2018

Я пытался проанализировать, какова будет временная сложность этого кода, но я застрял. Считаю ли я, что это O (n ^ 2) временная сложность из-за двух циклов for, или это просто O (n), потому что второй цикл for не всегда выполняется? С помощью этого кода я должен сканировать 2d массив на основе графика 

//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;
}

1 Ответ

0 голосов
/ 14 мая 2018

Если 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) возможных операций сложности O(log(n)) для O(n^3 log(n)) всего.

...