Реализация более эффективного алгоритма работает медленнее

Question

Я новичок здесь, и если мой вопрос не актуален, пожалуйста, удалите его. У меня были сомнения при решении следующей проблемы на LeetCode :

70 - Восхождение по лестнице: Вы поднимаетесь по лестнице. Требуется N шагов, чтобы достичь вершины. Каждый раз вы можете подняться на 1 или 2 шага. Каким образом вы можете подняться на вершину?

Примечание: Дано n будет положительным целым числом.

Пример 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.

Конечно, сложность времени вашего алгоритма сильно влияет на эффективность (извините, если это не актуально термин) вашего кода . Но для двух данных алгоритмов один может быть больше , эффективный для n < nmax value, а затем стать меньше для n >= nmax .

Посмотрите на этот график, взятый из Википедии ( Cmglee - лицензия CC BY-SA 4.0 , взята из статьи, указанной выше):

Кривая nlog2n, кажется, стоит больше , чем 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");

    }

}