algorithm - 离散数学 Big-O 符号 算法复杂度

Question

如果你能帮我做 a 部分，我可能会弄清楚 b 部分。我整天都在研究这个问题和类似的问题，但我只是在掌握如何处理嵌套循环方面遇到了问题。对于第一个循环有 n 次迭代，对于第二个循环有 n-1，对于第三个循环有 n-1.. 我是否正确地考虑了这个？

考虑以下算法，
它以 n 个整数 a1, a2, ..., an
作为输入并生成矩阵 M = {mij}
作为输出其中 mij 是最小项
在整数序列 ai, a + 1, ..., aj 对于 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) 比较的结论。

Answer 1

在 A 部分，您需要找到 min 的数量上限行动。

为了做到这一点，显然上面的算法less 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^3 min ops - 因此在你的算法中，less 然后 n^3最小操作数。

由此我们可以得出结论:#minOps <= 1 * n^3 (对于每个 n > 10，其中 10 是任意的)。
通过definition of Big-O , 这意味着算法是 O(n^3)

你说你一个人就能算B，那我就让你试试吧:)

---

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