管理员在白板考试期间提出了这个现在非常常见的算法问题。我的工作是观察，听取和客观地判断给出的答案，但是我既无法控制所提出的问题，也无法与回答者互动。给出了五分钟的时间来分析问题，候选人可以编写项目符号注释，伪代码（在实际的代码编写过程中以及在明确指出的情况下允许这样做，并且包括伪代码作为注释或TODO任务的人员）在弄清楚该算法之前获得了奖励积分）。
遇到此问题的人无法当场开始使用递归算法，因此监理人最终逐一将他引向了HIS解决方案，我认为这不是最佳选择（嗯，这与我选择的解决方案不同就代码优化而言，很难对某人进行客观评分）。
检察官：
public class Staircase { public static int stairs; public Staircase() { int a = counting(stairs); System.out.println(a); } static int counting(int n) { if (n < 0) return 0; else if (n == 0) return 1; else return counting(n - 1) + counting(n - 2) + counting(n - 3); } public static void main(String[] args) { Staircase child; long t1 = System.nanoTime(); for (int i = 0; i < 30; i++) { stairs = i; child = new Staircase(); } System.out.println("Time:" + ((System.nanoTime() - t1)/1000000)); } } //
矿：
public class Steps { public static int stairs; int c2 = 0; public Steps() { int a = step2(0); System.out.println(a); } public static void main(String[] args) { Steps steps; long t1 = System.nanoTime(); for (int i = 0; i < 30; i++) { stairs = i; steps = new Steps(); } System.out.println("Time:" + ((System.nanoTime() - t1) / 1000000)); } public int step2(int c) { if (c + 1 < stairs) { if (c + 2 <= stairs) { if (c + 3 <= stairs) { step2(c + 3); } step2(c + 2); } step2(c + 1); } else { c2++; } return c2; } }
输出： 控制器： 时间：356 矿井： 时间：166
有人可以澄清哪种算法更好/更优化吗？我的算法的执行时间似乎少于一半的时间（但是我正在引用和更新一个我认为是无关紧要的附加整数），并且它允许设置任意的开始和结束步骤，而无需先求出它们的差值（尽管对于高于n = 40的任何值，您将需要CPU的野兽）。
我的问题是：（随意忽略上述示例）如何正确地对基于递归的类似问题（河内塔等）进行基准测试。您只是看时间，还是考虑其他因素（堆？）。
前导广告：您可以在不到一毫秒的时间内轻松执行此计算。详细信息如下…
哪种算法“更好”的问题可能涉及执行时间，但也涉及其他方面，例如实现方式。
该Staircase实现更短，更简洁并且恕我直言更易读。更重要的是：它不涉及 状态 。c2您在此处引入的变量破坏了纯函数递归实现的优点（和美观）。这可能很容易解决，尽管那时的实现已经变得更加类似于该实现了Staircase。
Staircase
c2
关于执行时间的问题：在Java中正确地测量执行时间是很棘手的。
相关阅读：
为了正确可靠地衡量执行时间，存在几种选择。除了诸如VisualVM之类的探查器外，还有诸如JMH或Caliper之类的框架，但是诚然，使用它们可能需要一些努力。
对于最基本的手动Java Microbenchmark 的 最简单 形式，您必须考虑以下内容：
再次： 这些只是经验法则 ，仍然可能会出现意外结果（有关更多详细信息，请参见上面的链接）。但是使用这种策略，通常可以很好地了解性能，并且至少可以看到算法之间是否 真的 存在显着差异。
在Staircase实施和Steps执行都不是很不同的。
Steps
主要的概念不同的是，Staircase实现计数 下降 ，而Steps实现计数 了 。
实际影响性能的主要区别在于 基本案例 的处理方式（请参阅Wikipedia上的递归）。在您的实现中，避免不必要地递归调用该方法，而这会增加一些其他if语句的代价。该Staircase实现使用基本情况的非常通用的治疗，通过只是检查是否n < 0。
if
n < 0
可以考虑结合两种方法的思想的“中间”解决方案：
class Staircase2 { public static int counting(int n) { int result = 0; if (n >= 1) { result += counting(n-1); if (n >= 2) { result += counting(n-2); if (n >= 3) { result += counting(n-3); } } } else { result += 1; } return result; } }
它仍然是无状态的递归，并汇总中间结果，通过使用一些if查询避免了许多“无用”的调用。它已经比原始Staircase实现快得多，但仍然比Steps实现慢一点。
对于这两种实现，实际上都没有要计算的任何东西。该方法由少量if语句和一些附加内容组成。这里最昂贵的东西实际上是递归本身，带 有深度 嵌套的调用树。
这就是关键点：这是一个调用 树 。想象给定步骤数的计算结果，如“伪代码调用层次结构”：
compute(5) compute(4) compute(3) compute(2) compute(1) compute(0) compute(0) compute(1) compute(0) compute(0) compute(2) compute(1) compute(0) compute(0) compute(1) compute(0) compute(3) compute(2) compute(1) compute(0) compute(0) compute(1) compute(0) compute(0) compute(2) compute(1) compute(0) compute(0)
可以想象，当数字变大时，这个数字 呈指数增长 。并且所有结果都被计算了数百，数千或数百万次。这可以避免
加快计算速度的关键思想是使用动态编程。从根本上讲，这意味着将 存储 中间结果 以 供以后检索，这样就不必一次又一次地计算它们。
在本示例中实现了该示例，还比较了所有方法的执行时间：
import java.util.Arrays; public class StaircaseSteps { public static void main(String[] args) { for (int i = 5; i < 33; i++) { runStaircase(i); runSteps(i); runDynamic(i); } } private static void runStaircase(int max) { long before = System.nanoTime(); long sum = 0; for (int i = 0; i < max; i++) { sum += Staircase.counting(i); } long after = System.nanoTime(); System.out.println("Staircase up to "+max+" gives "+sum+" time "+(after-before)/1e6); } private static void runSteps(int max) { long before = System.nanoTime(); long sum = 0; for (int i = 0; i < max; i++) { sum += Steps.step(i); } long after = System.nanoTime(); System.out.println("Steps up to "+max+" gives "+sum+" time "+(after-before)/1e6); } private static void runDynamic(int max) { long before = System.nanoTime(); long sum = 0; for (int i = 0; i < max; i++) { sum += StaircaseDynamicProgramming.counting(i); } long after = System.nanoTime(); System.out.println("Dynamic up to "+max+" gives "+sum+" time "+(after-before)/1e6); } } class Staircase { public static int counting(int n) { if (n < 0) return 0; else if (n == 0) return 1; else return counting(n - 1) + counting(n - 2) + counting(n - 3); } } class Steps { static int c2 = 0; static int stairs; public static int step(int c) { c2 = 0; stairs = c; return step2(0); } private static int step2(int c) { if (c + 1 < stairs) { if (c + 2 <= stairs) { if (c + 3 <= stairs) { step2(c + 3); } step2(c + 2); } step2(c + 1); } else { c2++; } return c2; } } class StaircaseDynamicProgramming { public static int counting(int n) { int results[] = new int[n+1]; Arrays.fill(results, -1); return counting(n, results); } private static int counting(int n, int results[]) { int result = results[n]; if (result == -1) { result = 0; if (n >= 1) { result += counting(n-1, results); if (n >= 2) { result += counting(n-2, results); if (n >= 3) { result += counting(n-3, results); } } } else { result += 1; } } results[n] = result; return result; } }
我的PC上的结果如下：
... Staircase up to 29 gives 34850335 time 310.672814 Steps up to 29 gives 34850335 time 112.237711 Dynamic up to 29 gives 34850335 time 0.089785 Staircase up to 30 gives 64099760 time 578.072582 Steps up to 30 gives 64099760 time 204.264142 Dynamic up to 30 gives 64099760 time 0.091524 Staircase up to 31 gives 117897840 time 1050.152703 Steps up to 31 gives 117897840 time 381.293274 Dynamic up to 31 gives 117897840 time 0.084565 Staircase up to 32 gives 216847936 time 1929.43348 Steps up to 32 gives 216847936 time 699.066728 Dynamic up to 32 gives 216847936 time 0.089089
陈述顺序左右的小变化（“微优化”）可能会产生很小的影响，或产生显着的变化。但是使用完全不同的方法可以带来 真正的 改变。
