卷別

資料結構與演算法(A)

選擇

國立臺灣大學 2022 · 考試 · 第 20 題

(5 points) Given a graph $G = (V, E)$ with the adjacent matrix $W = w_{ij}$ with $W$ an $n \times n$ matrix. The following algorithm can compute the All-Pairs Shortest Path of $G$ .

FLOYD-WARSHALL'(W)
1  D = W
2  for k = 1, 2, ..., n
3      for i = 1, 2, ..., n
4          for j = 1, 2, ..., n
5              d_ij = min(d_ij, d_ik + d_kj)

What is the SPACE complexity of this algorithm?

(A)
$\Theta(n^2)$
(B)
$\Theta(n^3)$
(C)
$\Theta(n)$
(D)
$\Theta(n^4)$
(E)
none of the other choices

標準解析

AI 生成