如果你能帮我做 a 部分，我也许可以弄清楚 b 部分。我一整天都在研究这个问题和类似的问题，但我只是在掌握如何处理嵌套循环方面遇到问题。对于第一个循环，有 n 次迭代，第二次循环有 n-1 次迭代，第三次循环有 n-1 次迭代。我的想法正确吗？
考虑以下算法，
它将 n 个整数 a1, a2, ..., an 的序列作为输入
并生成矩阵 M = {mij}
作为输出
其中 mij 是最小项
在整数 ai、a + 1、...、aj 的序列中，j >= i，否则 mij = 0。
初始化 M，如果 j >= i 且 mij = 0，则 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) 比较。
最佳答案
在 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 ops - 因此在你的算法中，有更少然后 n^3最小操作数。
由此我们可以得出结论:#minOps <= 1 * n^3 (对于每个 n > 10，其中 10 是任意的)。
作者:definition of Big-O ，这意味着算法是 O(n^3)
你说你可以单独算出B，所以我让你试试:)
提示:中间循环比for j=i+1 to n/2有更多次迭代
关于algorithm - 离散数学 Big-O 表示法 算法复杂性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12883484/