小编kkm*_*kkm的帖子

如果你能帮助我做一部分,我可能会弄清楚b部分.我一整天都在看这个和类似的问题,我只是在掌握嵌套循环的问题时遇到了问题.对于第一个循环,有n次迭代,第二次循环有n-1,第三次有n-1 ..我是否正确地思考这个问题？

考虑以下算法,
该算法将n个整数a1,a2,...,a的序列作为输入,
并将矩阵M = {mij}作为输出
,其中mij是
整数序列中的最小项ai,a + 1 ,...,aj为j> = i,mij = 0否则.

如果j> = i且mij = 0,则初始化M使得mij = ai

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)比较.