这是算法分析是正确的
问题描述:
我读的算法设计手册和这个解决方案是不说明书中无。我花了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
我们解决第一个求和,我们得到
最终的公式应该是:
鉴于第n^4负,我们可以得出结论,该算法的运行时间为
它是正确的吗?
答
最终结果是正确的,详细计算中至少有一个错误:从a到b在1之上的和是b-a + 1。
此外,下一个词的符号是不相关的(我假设你的意思是n^2)。即使n^2项是正数,运行时也是Theta(n^3)。
第二次看我知道我错把2n个为2N^2,这就是为什么我有着N^4之后。关于总和的事情,你能指出错误吗? – SuburbanFilth
我以为我这样做:如果你总结1从a到b的界限,结果是b-a + 1而不仅仅是b-a。 – Henry
mb again lel,我没有正确阅读这个句子 – SuburbanFilth