离散数学Big-O表示法算法复杂性

Question

如果你能帮助我做一部分,我可能会弄清楚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)比较.

Answer 1

在A部分中,您需要找到min操作数的上限.

为了做到这一点,很明显上面的算法具有较少的 min操作,然后如下:

for i=1 to n
  for j=1 to n //bigger range then your algorithm
    for k=1 to n //bigger range then your algorithm
        (something with min)

上述具有恰好 N R个3个minOPS -从而在你的算法,也有更小然后n^3分钟OPS.

由此我们可以得出结论:( #minOps <= 1 * n^3对于每个n> 10,其中10是任意的).
根据Big-O的定义,这意味着算法是O(n^3)

你说你可以单独做B,所以我会让你试试:)

提示:中间循环有更多的迭代for j=i+1 to n/2