Рекурсивный алгоритм Сложность времени: смена монет

Я перебрал некоторые алгоритмы и наткнулся на обмен монет проблема.

Размышляя о проблеме, я придумал это наивное рекурсивное решение:

int coinChange(const vector<int>& coins, int start, int n) {
if (n == 0) return 1;
if (n < 0) return 0;

int total = 0;

for (int i = start; i < coins.size(); ++i) {
if (coins[i] <= n) total += coinChange(coins, i, n-coins[i]);
}

return total;
}

Затем я понял, что «принятое» решение было следующим:

int count( int S[], int m, int n )
{
// If n is 0 then there is 1 solution (do not include any coin)
if (n == 0)
return 1;

// If n is less than 0 then no solution exists
if (n < 0)
return 0;

// If there are no coins and n is greater than 0, then no solution exist
if (m <=0 && n >= 1)
return 0;

// count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1]
return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}

Сначала я думал, что эти два были по существу одинаковыми. Мне было ясно, что мое дерево рекурсии было намного шире, но казалось, что это было только потому, что мой алгоритм выполнял больше работы на каждом уровне, поэтому он выровнялся. Похоже, что оба алгоритма рассматривают количество способов внесения изменений в текущую монету (учитывая, что это <= текущая сумма), и учитывая количество способов внести изменения без текущей монеты (таким образом, со всеми элементами в массиве монет минус текущая монета). Поэтому параметр start в моем алгоритме делал по существу то же самое, что и m делает во втором алгоритме.

Чем больше я смотрю на это, тем не менее, кажется, что независимо от предыдущего текста, мой алгоритм O(n^n) а второй O(2^n), Я смотрел на это слишком долго, но если бы кто-то мог объяснить, какую дополнительную работу выполняет мой алгоритм по сравнению со вторым, это было бы здорово.

РЕДАКТИРОВАТЬ

Я понимаю динамическое программирование решения этой проблемы, этот вопрос является чисто сложным вопросом.

5

Решение

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

Например, вот частичная оценка второго count в случае, когда S = [1, 5, 10] и m = 3. В каждой строке я расширяю самое левое определение count,

  count(S, 3, 100)
= count(S, 2, 100) + count(S, 3, 90)
= count(S, 1, 100) + count(S, 2, 95) + count(S, 3, 90)
= count(S, 0, 100) + count(S, 1, 99) + count(S, 2, 95) + count(S, 3, 90)
= 0 + count(S, 1, 99) + count(S, 2, 95) + count(S, 3, 90)

Вы можете видеть, что это тот же расчет, что и ваш цикл for, который подводит итог total,

Оба алгоритма ужасны, потому что они работают в экспоненциальном времени. Вот ответ (мой), который использует метод аккуратного динамического программирования, который выполняется за время O (nm) и использует O (n) память, и является чрезвычайно сжатым — сопоставимым по размеру с вашим наивным рекурсивным решением. https://stackoverflow.com/a/20743780/1400793 . Это на Python, но его легко конвертировать в C ++.

3

Другие решения

Вы не прочитали всю статью (?).

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

Что касается того, почему ваше решение n ^ n, а их исходное решение 2 ^ n. Оба решения на самом деле 2 ^ (n + # монет). Они просто вызывают функцию с помощью m-1 вместо цикла, который проходит через каждую монету. В то время как ваше решение пробует каждую монету в начале, а затем все реже и реже, оно пытается взять одну монету типа m, затем другую, затем другую, пока в какой-то момент не переключится на тип m-1 и не сделает то же самое с ней и так на. В основном оба решения одинаковы.

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

Оба решения верны, поэтому они достигнут всех возможных решений, и оба прекратят выращивать определенную ветвь рекурсии, как только она достигнет отрицательного n. Поэтому они имеют одинаковую сложность.

И если вы не уверены, просто попробуйте каждое решение, кроме добавления некоторого счетчика и увеличивайте его при каждом входе в функцию. Сделайте это для каждого решения, и вы увидите, что вы получите тот же номер.

1

эталонный тест
На моем компьютере тесты следующие:

coinChange(v, 0, 500);// v=[1, 5, 10, 15, 20, 25]

Потребовалось 1,84649 с.
Но

count(s, 6, 500); //s = [1, 5, 10, 15, 20, 25]

потребовалось 0.853075s, чтобы выполнить.

РЕДАКТИРОВАТЬ

Я интерпретирую результат, поскольку временная сложность двух алгоритмов одинакова.

0
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector