这个现在非常常见的算法问题是监考老师在白板考试中问的。我的工作是观察、倾听和客观判断给出的答案，但我既无法控制所问的问题，也无法与回答者互动。有五分钟的时间来分析这个问题，候选人可以写项目符号注释、伪代码（只要有明确的指示，这在实际代码编写过程中也是允许的，在计算出算法之前，将伪代码作为注释或TODO任务的人可以获得加分）。
- "一个孩子正在用n步爬上楼梯，一次可以跳1步、2步或3步。实施一种方法来计算孩子可以跳上楼梯的方式。"
得到这个问题的人无法当场开始递归算法，所以监考者最终一块一块地把他引向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）。
我的问题是：（可以忽略上面的例子）如何正确地对类似的基于递归的问题（河内塔等）进行基准测试。你只是看时间，还是考虑其他因素（堆？）。
Teaser：您可以在不到一毫秒的时间内轻松执行此计算。详细信息如下。。。
哪一个"更好"
哪种算法"更好"的问题可能涉及执行时间，但也涉及其他方面，比如实现风格。
Staircase实现更短、更简洁并且IMHO更可读。更重要的是：它不涉及状态。您在那里引入的c2变量破坏了纯函数递归实现的优点（和美感）。这可能很容易解决，尽管实现方式已经变得更类似于Staircase。
测量性能
关于执行时间的问题：在Java中正确地测量执行时间是很棘手的。
相关阅读：
- 如何用Java编写正确的微基准测试
- Java理论与实践：剖析一个有缺陷的微基准
- 热点内部
为了正确可靠地测量执行时间，有几种选择。除了像VisualVM这样的探查器之外，还有像JMH或Caliper这样的框架，但无可否认，使用它们可能需要一些努力。
对于最简单的形式的非常基本的手动Java微基准，您必须考虑以下内容：
- 多次运行算法，让JIT有机会发挥作用
- 交替运行算法，而不是一个接一个
- 随着输入大小的增加运行算法
- 以某种方式保存并打印计算结果，以防止计算被优化掉
- 在基准测试期间，不要将任何内容打印到控制台
- 请考虑定时可能会被垃圾收集器（GC）扭曲
再次：这些只是经验法则，可能仍会出现意外结果（有关更多详细信息，请参阅上面的链接）。但使用这种策略，您通常可以获得关于性能的良好指示，并且至少可以看到算法之间是否真的存在显著差异。
两种方法之间的差异
Staircase实现和Steps实现没有太大区别。
主要的概念差异是Staircase实现是向下计数，而Steps实现是向上计数。
实际影响性能的主要区别是基本用例的处理方式（请参阅维基百科上的递归）。在您的实现中，避免在不必要时递归调用该方法，代价是一些额外的if语句。Staircase实现使用了对基本情况的非常通用的处理，只需检查是否为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语句和一些附加语句组成。这里最昂贵的实际上是递归本身，带有deeeep嵌套调用树。
这里的关键点是：这是一个调用树。想象一下，对于给定数量的步骤，它正在计算什么，作为"伪代码调用层次结构"：
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;
}
}
在我的电脑上的结果如下：
...
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
语句顺序的微小变化（"微观优化"）可能会产生较小的影响，或产生显著的差异。但是，使用完全不同的方法可以使产生真正的差异。