这个算法分析正确吗？

Question

3

我正在阅读《算法设计手册》，但这个解决方案并没有在书中提到。我花了大约30分钟的时间来理解它，所以想知道它是否正确。下面是该函数的伪代码：

function conundrum(n)
  r:=0
  for i:=1 to n do
    for j:=i+1 to n do
      for k:=i+j−1 to n do
        r:=r+1

$\sum_{i=1}^{n}\sum_{j=i+1}^{n}\sum_{k=i+j-1}^{n}1$

我们解决第一个求和，得到：

$\sum_{i=1}^{n}\sum_{j=i+1}^{n}(n - i - j + 1)$

$\sum_{i=1}^{n}(n^2 - 5n - 2 - i^2 - 3i)$

最终等式应该是：

$n^3 - 5n^2 - 2n - \frac{n(n+1)(2n+1)}{6} - \frac{3n(n+1)}{2}$

鉴于n^4为负，我们可以得出该算法的运行时间是 $\Theta (n^3)$ 。这正确吗？

- Martin Spasov

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Henry · Accepted Answer

最终结果是正确的，但详细计算中至少有一个错误：从a到b求和，1的和为b-a+1。

此外，下一项的符号无关紧要（我猜你的意思是n^2）。即使n^2项是正数，运行时间仍然是Theta(n^3)。