时空权衡

Question

我被问到一个测验以下问题,并且在提示设计更有效的代码段时不知道该问我自己.我的意思是我知道 - 如果 - 其他是耗费时间,我想也许是for循环？我很好奇是否有人可以A.告诉我是否只有1个答案而且B.告诉我为什么解决方案可以运行得更快.

它说:假设以下代码段非常耗时,请编写一个至少削减运行时间2分钟的段.

if (f(n)%==0)
  key = 3*f(n)+4*f(n)+7;
else 
  key = 6*f(n)*f(n)-33;

Answer 1

"我的意思是我知道 - 如果 - 其他时间很长,我想也许是一个for循环"这是不正确的.考虑一下这里真正耗时的事情.提示:f(n)可能做很多事情.但如果代码需要很长时间才能处理,那么唯一最好的选择就是f(n)罪魁祸首.这里发生的唯一另一件事if-statement是快速的,还有一些算法(计算机非常快).

幸运的是,您正在多次计算f(n)固定输入n!通过将此方法的输出保存在变量中然后仅使用变量来节省您的麻烦.我不知道你或你的老师在哪里"2分钟",这在我看来是任意的废话.

Answer 2

需要注意的是,f(n)在所有情况下都会被调用3次.如果我们假设这是瓶颈,那么我们希望最小化我们调用该函数的次数.

另请注意,f(n)的结果是常数(假设没有外部因素).因此,您只需要计算一次.