2

如果你能帮我做 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) 比较的结论。

4

2 回答 2

5

在 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^3 个min操作 - 因此在您的算法中，操作少于n^3最小操作。

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

你说你一个人就能搞定B，那我就让你试试吧：）

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

于 2012-10-14T15:21:57.403 回答
0

对于外部循环的每次迭代，内部两个嵌套循环会给出n^2复杂度 if i == n。外循环将运行 for i = 1 to n。所以总复杂度将是一个系列，如：1^2 + 2^2 + 3^2 + 4^2 + ... ... ... + n^2. 这个总和值为n(n+1)(2n+1)/6。忽略这个求和项的低阶项，最终的顺序是O(n^3)

于 2012-10-14T15:40:18.137 回答