Как рассчитать алгоритм динамического программирования (Memoization) Big O

Question

Как бы я мог вычислить большой O алгоритма DP. Я понял, что мои методы расчета алгоритмов не всегда работают. Я бы использовал простые трюки, чтобы извлечь то, что было Big O. Например, если бы я оценивал не memoized версию алгоритма ниже (удаление механизма кэширования), я бы посмотрел, сколько раз рекурсивный метод называл себя в этом случае 3 раза. Тогда я повысил бы это значение до n, давая O (3^n). С DP, который не совсем прав, потому что рекурсивный стек не идет так глубоко. Моя интуиция подсказывает мне, что Big O решения DP будет O (n^3). Как мы устно объясним, как мы пришли к этому ответу. Что еще важно, что такое техника, которая может быть использована для поиска Big O подобных проблем.. Поскольку это DP, я уверен, что число подвыборок важно , как мы вычислим количество вспомогательных проблем.

public class StairCase { 
    public int getPossibleStepCombination(int n) { 
     Integer[] memo = new Integer[n+1]; 
     return getNumOfStepCombos(n, memo); 
    } 

    private int getNumOfStepCombos(int n, Integer[] memo) { 
     if(n < 0) return 0; 
     if(n == 0) return 1; 
     if(memo[n] != null) return memo[n]; 
     memo[n] = getNumOfStepCombos(n - 1, memo) + getNumOfStepCombos(n - 2, memo) + getNumOfStepCombos(n-3,memo); 
     return memo[n]; 
    } 
} 

Answer 1

Первые 3 линии ничего не делать, но сравнивать int значения, доступ к массиву по индексу, и посмотреть, если Integer ссылка null. Все это O(1), поэтому вопрос в том, сколько раз метод называется рекурсивно.

Этот вопрос очень сложный, поэтому я обычно обманываю. Я просто использую счетчик, чтобы посмотреть, что происходит. (Я сделал ваши методы статичными для этого, но в целом вам следует избегать статического изменчивого состояния, где это возможно).

static int counter = 0; 

public static int getPossibleStepCombination(int n) { 
    Integer[] memo = new Integer[n+1]; 
    return getNumOfStepCombos(n, memo); 
} 

private static int getNumOfStepCombos(int n, Integer[] memo) { 
    counter++; 
    if(n < 0) return 0; 
    if(n == 0) return 1; 
    if(memo[n] != null) return memo[n]; 
    memo[n] = getNumOfStepCombos(n - 1, memo) + getNumOfStepCombos(n - 2, memo) + getNumOfStepCombos(n-3,memo); 
    return memo[n]; 
} 

public static void main(String[] args) { 
    for (int i = 0; i < 10; i++) { 
     counter = 0; 
     getPossibleStepCombination(i); 
     System.out.print(i + " => " + counter + ", "); 
    } 
} 

Эта программа печатает

0 => 1, 1 => 4, 2 => 7, 3 => 10, 4 => 13, 5 => 16, 6 => 19, 7 => 22, 8 => 25, 9 => 28, 

так это выглядит, как конечные значения счетчика задается 3n + 1.

В более сложном примере, возможно, я не смогу определить шаблон, поэтому я ввожу первые несколько номеров (e.g. 1, 4, 7, 10, 13, 16) в Online Encyclopedia of Integer Sequences, и я обычно берусь на страницу, содержащую простую формулу для шаблона.

Как только вы обманули таким образом, чтобы узнать правило, вы можете понять, почему правило работает.

Вот как я понимаю, откуда приходит 3n + 1. Для каждого значения n вы только должны сделать линии

memo[n] = getNumOfStepCombos(n - 1, memo) + getNumOfStepCombos(n - 2, memo) + getNumOfStepCombos(n-3,memo); 

ровно один раз. Это связано с тем, что мы записываем результаты и делаем это только в том случае, если ответ еще не был рассчитан.

Поэтому, когда мы начинаем с n == 5, мы запускаем эту строку exacly 5 раз; один раз для n == 5, один раз с n == 4, один раз с n == 3, один раз с n == 2 и один раз с n == 1. Итак, это 3 * 5 == 15 раз метод getNumOfStepCombos получает вызов от себя. Метод также вызывается один раз извне (от getPossibleStepCombination), поэтому общее количество вызовов составляет 3n + 1.

Таким образом, это алгоритм O(n).

Если алгоритм имеет линии, которые не являются O(1), этот метод счетчика не может использоваться напрямую, но вы можете часто адаптировать подход.

Answer 2

Ответ Павла технически не прав, но немного вводит в заблуждение. Мы должны вычислять большую O-запись тем, как функция реагирует на изменения размера ввода. Ответ Павла O (n) делает сложность линейной, когда она действительно экспоненциальна для количества бит, необходимых для представления числа n. Так, например, n = 10 имеет ~ 30 вычислений и m = 2 бита. n = 100 имеет ~ 300 расчетов и m = 3 бит. n = 1000 имеет ~ 3000 вычислений и m = 4 бит.

Я считаю, что сложность вашей функции будет O (2^m), где m - количество бит, необходимое для представления n. Я упомянул https://www.quora.com/Why-is-the-Knapsack-problem-NP-complete-even-when-it-has-complexity-O-nW для моего большого ответа.