以下代码的复杂度是多少?是 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
构造minimum_spanning_tree的复杂度是O(n^2)。在最小生成树中查找最短路径的复杂度是多少?是 O(nlog(n)) 吗?
代码基于Madhav-99的代码,参见:
这是添加了关于 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
鉴于
MST = nx.minimum_spanning_tree(G)
的复杂度为 O(n²)。
现在添加循环的复杂性:
O(n) (inner loop)
+ O(n log n) (`nx.shortest_path`)
= O(n log n)
* O(n²) (outer loops)
= O(n³ log n)
现在我们有三个复杂性:
由于 O(n3 log n) > O(n2)(读作:O(n3 log n) 支配 O(n2),cal_minimax_path_matrix(n) 的整体复杂度为 O(n3 log n)。
参考资料:
[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