如果你能帮我做 a 部分,我可能会弄清楚 b 部分。我整天都在研究这个和类似的问题,我只是在掌握如何处理嵌套循环时遇到问题。对于第一个循环有 n 次迭代,对于第二个有 n-1,对于第三个有 n-1 .. 我在想这个正确吗?
考虑以下算法,
该算法将 n 个整数序列 a1, a2, ..., an作为输入,
并生成矩阵 M = {mij} 作为输出,其中 mij 是
整数序列 ai, a + 1 中
的最小值
, ..., aj for j >= i 和 mij = 0 否则。
初始化 M 使得 mij = ai 如果 j >= i 并且 mij = 0
for i:=1 to n do
for j:=i+1 to n do
for k:=i+1 to j do
m[i][j] := min(m[i][j], a[k])
end
end
end
return M = {m[i][j]}
(a) 证明该算法使用 Big-O(n^3) 比较来计算矩阵 M。
(b) 证明该算法使用 Big-Omega(n^3) 比较来计算矩阵 M。
使用这张脸和 (a) 部分,得出该算法使用 Big-theta(n^3) 比较的结论。