Сложность рекурсии во вложенных циклах в программировании Dynami c и Non-Dynami c

Question

Я написал базовый c пример динамического программирования c в Java (показан ниже), который решает проблему самой длинной возрастающей подпоследовательности (https://en.wikipedia.org/wiki/Longest_increasing_subsequence).

Функция работает, но для домашнего задания я пытаюсь выяснить временную сложность этого алгоритма по сравнению с его нединамическим c эквивалентом.

Я считаю, что версия Dynami c - это O (n ^ 2), но для нединамического c эквивалента я очень запутался. Я пытался написать неудачную c версию, но не смог написать, но думаю, что она будет состоять из рекурсивного вызова внутри nested (2) для циклов . Будет ли это означать экспоненциальную сложность времени? Или даже факторная сложность времени?

Я был бы очень признателен за любую помощь в разгадке этой загадки сложности или даже в создании нединамического c, рекурсивного эквивалента функции, которую я написал ниже.

Заранее спасибо!

   public static int longest(int[] array) {

        int n = array.length;

        int[] results = new int[n];

        for(int i = 0; i < n; i++) {
            results[i] = -1;
        }

        int max = 1;
        for(int j = 1; j <= n; j++) {
            int current = memoized_longest(array, j, results);
            if(current > max) {
                max = current;
            }
        }

        return max;
    }


    public static int memoized_longest(int[] array, int n, int[] results) {

        if(results[n-1] >= 0) {
            return results[n-1];
        }

        if(n == 1) {
            results[n-1] = 1;
            return results[n-1];
        }

        int q = 1;

        for(int i = n - 1; i >= 0; i--) {
            if(array[i] < array[n - 1]) {
                 q = Math.max(q, 1 + memoized_longest(array, i+1, results));
            }
        }

        results[n-1] = q;
        return q;
    }

Answer 1

У вас почти было это:

public static int longest(int[] array) {
  int q = 0;
  for (int i = 0; i < array.length; i++) {
    q = Math.max(q, longest_at(array, i));
  }
  return q;
}

public static int longest_at(int[] array, int i) {
  int q = 1;
  for (int j = 0; j < i; j++) {
    if (array[j] < array[i]) {
      q = Math.max(q, 1 + longest_at(array, j));
    }
  }
  return q;
}

longest_at возвращает длину самой длинной увеличивающейся подпоследовательности, заканчивающейся в позиции i. Превращение рекурсивного алгоритма DP в обычный рекурсивный алгоритм достигается простым отбрасыванием запоминания.

Что касается времени выполнения, мы имеем следующее рекуррентное соотношение:

T (n) <= T ( 1) + T (2) + ... + T (n-1) </p>

T (n) - время выполнения longest_at(n). Чтобы вычислить longest_at(n), мы должны (потенциально, если все элементы до позиции n меньше array[n]) вычислить longest_at(1), longest_at(2), до longest_at(n-1). Это отражается в рекуррентном соотношении.

Если T (1) = 1, то T (n) = 2 ^ n - 1 является решением.