我正在阅读《算法设计手册》,但这个解决方案并没有在书中提到。我花了大约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
我正在阅读《算法设计手册》,但这个解决方案并没有在书中提到。我花了大约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
最终结果是正确的,但详细计算中至少有一个错误:从a到b求和,1的和为b-a+1。
此外,下一项的符号无关紧要(我猜你的意思是n^2)。即使n^2项是正数,运行时间仍然是Theta(n^3)。