时间space权衡

Question

我在测验中被问到以下问题，当提示我设计更高效的代码段时，我不知道该问自己什么。我的意思是我知道 if-else 很耗时，我在想也许是一个 for 循环？我很好奇是否有人可以 A. 告诉我是否只有 1 个答案，然后 B. 告诉我为什么解决方案可能运行s 如此之快。

它说：假设下面的代码段很耗时，写一段至少可以节省运行时间的2分钟。

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

Answer 1

"I mean I know if-else are time consuming, I was thinking maybe a for loop" 这是不正确的。想想这里发生的事情实际上 很耗时。提示：f(n) 可以做很多事情。但是如果代码需要很长时间来处理，那么唯一最好的选择就是 f(n) 是罪魁祸首。这里唯一发生的另一件事是 if-statement ，它很快，还有一些算术（计算机在这方面非常快）。

幸运的是，您正在多次计算固定输入 n 的 f(n)！通过将此方法的输出保存在变量中然后仅使用该变量来省去麻烦。我不知道你或你的老师从哪里得到的“2 分钟”，在我看来那是胡说八道。

Answer 2

需要注意的是 f(n) 在所有情况下都会被调用 3 次。如果我们假设这是瓶颈，那么我们希望尽量减少调用该函数的次数。

还要注意，f(n) 的结果是一个常数（假设没有外部因素）。因此，您只需计算一次。

Answer 3

如果你的教授说你需要从代码中节省两分钟，那么你可以说代码至少需要两分钟来计算。您在代码中计算了 3 次 f(n)，那么假设没有缓存，可以肯定地说每次 f(n) 计算大约需要 40 秒。然后，通过在开始时计算一次 f(n) 并保存结果以在其他四个调用中使用它，将为您节省 40*2 秒。

像这样：

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

Answer 4

根据小测验，优化后的代码段将节省至少两分钟的时间。您可以推断给定的代码段至少需要两分钟的时间来计算。

无论条件 if 语句的结果如何，您在给定代码段中调用了 f(n) 3 次。

通过在开始时计算一次f(n)，并将值赋给一个变量，以供后续计算使用...

像这样：

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

...您将减少 执行时间 (2 x 执行时间 f(n) 调用) - (声明变量并为其赋值的执行时间 + ( 2 x execution time of reading value from that variabl). 声明和赋值，读取值的执行时间从该变量开始，给定代码中的其他语句（如 if 语句和逻辑表达式操作）无关紧要（可能小于 1 毫秒）。

根据预期结果，您可以推断出每次调用 f(n) 至少需要 1 分钟才能执行；再次迭代，给定代码段执行收益与现在优化的代码段执行收益之间的时间差为 2 分钟。

时间space权衡

Time space trade-off

java

math

for-loop

if-statement