Início / coding / Perguntas / 78713704
Accepted
Mike Mathcook
Asked: 2024-07-06 10:05:57 +0800 CST

Qual é a complexidade do código a seguir? É O(n^3log(n))?

  • 772

Qual é a complexidade do código a seguir? É O(n^3log(n))?

#G is an undirected dense graph, which has N vertices.
import networkx as nx
def cal_minimax_path_matrix(G):
    MST = nx.minimum_spanning_tree(G)
    minimax_matrix = np.zeros((N, N))

    for i in range(N):
        for j in range(N):
            if j > i:
                max_weight = -1 
                path = nx.shortest_path(MST, source=i, target=j)
                for k in range(len(path)-1):
                    if( MST.edges[path[k],path[k+1]]['weight'] > max_weight):
                        max_weight = MST.edges[path[k],path[k+1]]['weight']
                minimax_matrix[i,j] = minimax_matrix[j,i] = max_weight
                
    return minimax_matrix

A complexidade de construir uma árvore_spanning_mínima é O(n^2). Qual é a complexidade de encontrar o caminho mais curto em uma árvore mínima_spanning? É O(nlog(n))?

O código é baseado no código de Madhav-99, veja:

https://github.com/Madhav-99/Minimax-Distance

graph-theory

1 respostas

  1. Best Answer

    Este é o código com comentários adicionados sobre a complexidade de cada seção em O:

    #G is an undirected dense graph, which has N vertices.
import networkx as nx
def cal_minimax_path_matrix(G):
    MST = nx.minimum_spanning_tree(G) # O(n²) (given)
    minimax_matrix = np.zeros((N, N)) # O(n²) (Initializes a NxN matrix, takes NxN time)

    for i in range(N): # O(n) (loop)
        for j in range(N): # O(n) (loops combined: O(n)*O(n)=O(n²))
            if j > i:
                max_weight = -1 # O(1) (constant)
                path = nx.shortest_path(MST, source=i, target=j) # Uses Dijkstra algorithm by default [1], which is O(ElogV) [2], applied to a minimum spanning tree this will be O(V-1 log V) [3] -> O((n-1) log n) -> O(n log n)
                for k in range(len(path)-1): # O(n) as the path can be at most n long
                    if( MST.edges[path[k],path[k+1]]['weight'] > max_weight):
                        max_weight = MST.edges[path[k],path[k+1]]['weight']
                minimax_matrix[i,j] = minimax_matrix[j,i] = max_weight
                
    return minimax_matrix

    dada a complexidade de MST = nx.minimum_spanning_tree(G)é O (n²).

    Agora somando a complexidade dos loops:

    O(n) (inner loop)
+ O(n log n) (`nx.shortest_path`)
= O(n log n)
* O(n²) (outer loops)
= O(n³ log n)

    Agora temos três complexidades:

    • O(n²) para inicializar o MST
    • O(n²) para inicializar a matriz
    • O(n³ log n) para o loop

    Como O(n³ log n) > O(n²) (leia-se: O(n³ log n) domina O(n²)), a complexidade geral de cal_minimax_path_matrix(n) é O(n³ log n).

    Referências:
    [1] https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.generic.shortest_path.html
    [2] https://stackoverflow.com/a/26548129/8517948
    [3] https://math.stackexchange.com/questions/1524709/minimum-spanning-tree-edge-count

    • 1

relate perguntas