java - 为什么更高效的算法运行速度更慢？

Question

我是新来的，如果我的问题不相关，请删除它。我在解决 LeetCode 上的以下问题时有疑问:

70 - Climbing Stairs: You are climbing a stair case. It takes N steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

示例1:

• 输入:2
• 输出:2

说明:有两种方法可以爬到山顶。

1. 一步然后另一步

2. 一次两步。

我知道这个问题的两个解决方案:

• 在每一步计算所有可能的步骤组合:

  public class Solution {
      public int climbStairs(int n) {
          climb_Stairs(0, n);
      }
      public int climb_Stairs(int i, int n) {
          if (i > n) {
              return 0;
          }
          if (i == n) {
              return 1;
          }
          return climb_Stairs(i + 1, n) + climb_Stairs(i + 2, n);
      }
  }
  

• 另一种使用动态规划:

  public class Solution {
      public int climbStairs(int n) {
          if (n == 1) {
              return 1;
          }
          int[] dp = new int[n + 1];
          dp[1] = 1;
          dp[2] = 2;
          for (int i = 3; i <= n; i++) {
              dp[i] = dp[i - 1] + dp[i - 2];
          }
          return dp[n];
      }
  }
  

很明显，第二种方法比第一种方法效率高得多。然而，当我提交它们时，LeetCode 显示了几乎相同的运行时间，大约 4 毫秒。第二个的运行时间不应该比第一个短得多吗？

Answer 1

我用不同的步数测试了您的实现。代码如下，位于答案末尾。

• 3 步骤，n = 3 ，我得到了这个输出:

  Time spent for 3 step(s):
       - climbStairsByComputingAllNextSteps(): 6243 nanoseconds
       - climbStairsDynamically(): 25236 nanoseconds
  

哦，效率是不是越慢？好吧，让我们再做一次测试:

• 20 步，n = 20 ，我得到了这个输出:

  Time spent for 20 step(s):
       - climbStairsByComputingAllNextSteps(): 1048360 nanoseconds
       - climbStairsDynamically(): 5657 nanoseconds
  

因此，您的实现效率取决于 n .

当然，time complexity 算法对代码的效率(抱歉，如果不是相关术语)有很大影响。但对于两种给定的算法，其中一种算法对于 n < nmax value 来说可能更高效。 ，然后成为n >= nmax的少那个。

看看这张取自维基百科的图表(由 Cmglee - 许可 CC BY-SA 4.0 ，取自上面链接的文章):

nlog <子> 2 n 曲线似乎比 n 的成本更多 一，除了 0 附近 (0 <= n < ~1) 。这个街区可能会有所不同。在这里，他们的效率切换点似乎是n=6 。

低于我使用的工作示例(尝试使用 Online Java Compiler )。

public class Solution {
    public static void climbStairsByComputingAllNextSteps(int n) {
        processNextClimbingByComputingAllNextSteps(0, n);
    }
    private static int processNextClimbingByComputingAllNextSteps(int i, int n) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        return
        processNextClimbingByComputingAllNextSteps(i + 1, n) +
        processNextClimbingByComputingAllNextSteps(i + 2, n);
    }

    public static int climbStairsDynamically(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
    long startTime, diffTime;
    int steps;

    try {
        steps= Integer.parseInt(args[0]);
    } catch (Exception e) {
        steps=10;
    }

    System.out.println("Time spent for " + steps + " step(s):");
    System.out.print("\t - climbStairsByComputingAllNextSteps(): ");
    startTime = System.nanoTime();
    climbStairsByComputingAllNextSteps(steps);
    diffTime = System.nanoTime() - startTime;
    System.out.println(diffTime + " nanoseconds");
    System.out.print("\t - climbStairsDynamically(): ");
    startTime = System.nanoTime();
    climbStairsDynamically(steps);
    diffTime = System.nanoTime() - startTime;
    System.out.println(diffTime + " nanoseconds");

    }

}