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

如果你能帮我做part a，我大概可以找出b部分。我一整天都在看这个和类似的问题，而我只是在解决如何处理嵌套循环时遇到问题。对于第一个循环，有n次迭代，第二次有n-1次，第三次有n-1次。我是否正确思考这个问题？离散数学Big-O符号算法复杂性

考虑下面的算法，
，其作为输入n个整数a1的一个序列，A2，...，一个
，并产生作为输出的矩阵M = {}自我介绍
其中自我介绍是最小术语
在整数ai，a + 1，...，aj的序列中，j> = i，否则mij = 0。

初始化中号以便自我介绍=人工智能如果j> = i和自我介绍= 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））比较。

来源

2012-10-14 kkm

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

为了做到这一点，很显然，上述算法具有少min OPS然后执行以下操作：

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)

上面有正是ñ^ 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

来源

2012-10-14 15:21:57 amit

谢谢！这比教材中的其他例子更有意义。现在，对于b部分。看看你的提示，如果我只看前半部分，操作次数会少一些，但算法仍然会执行Cn^3操作，其中C <= 1。因此，该算法是Big-Omega（n^3）。那是对的吗？ – kkm

@helmeplease：这个想法是正确的，但是如果你正式需要，那么应该做更多的步骤来展示它，然后如此直截了当。试试看，使用我用来展示big-O的方法，经过几次试验后，我相信你会到达那里。 – amit

我必须说明这个新算法有多少操作，或者我可以说“Cn^3操作，其中C <= 1？”这是我遇到的最大问题 - 计算操作次数，当它不像您提供的示例那样简单时。 – kkm

对于外部循环内部的每次迭代，如果有i == n，则两个嵌套循环将给出n^2复杂度。外环将运行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-14 15:40:18 taufique

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

回答

相关问题