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

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

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

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). Я слишком долго смотрел на это, но если бы кто-нибудь мог объяснить, какую дополнительную работу выполняет мой алгоритм по сравнению со вторым, это было бы здорово.

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

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


c++ recursion algorithm time-complexity coin-change
person Dominic Farolino    schedule 18.07.2016    source источник
comment
Возможно, это не относится к делу, но хотя алгоритмы O (2 ^ n), это не жесткая граница. То есть независимо от значения S[] алгоритм не является Theta(2^n). Например, когда m = 2, наихудшим случаем является S = [1, 2], а сложность — Theta (Fib (n)) = Theta (phi ^ n), где phi — это золотое сечение.   -  person Paul Hankin    schedule 18.07.2016
comment
@PaulHankin Хороший вопрос. Итак, чтобы сказать, что эти алгоритмы являются тета (2 ^ n), насколько я понимаю, нам нужно найти n_sub_0 такое, что f (n) = O (2 ^ n) и f (n) = Omega (2 ^ n). ), для всех n >= n_sub_0, можно ли это сделать в данной конкретной ситуации?   -  person Dominic Farolino    schedule 18.07.2016
comment
Дом, я не уверен, что понимаю, о чем ты спрашиваешь. Если вы спрашиваете, можно ли найти константу c такую, что c * phi^n ›= 2^n для всех больших n, то относительно легко показать, что это не так.   -  person Paul Hankin    schedule 18.07.2016
comment
@PaulHankin Извините, позвольте мне попытаться прояснить это. Мне интересно, можно ли либо установить жесткие границы для этого алгоритма, чтобы f (n) = Theta (x), либо мы можем показать, что для всех входных данных, превышающих некоторый порог, f (n) = Theta (2 ^ н). Я упоминаю об этом, потому что кажется, что ваш пример вводит небольшой ввод, чтобы показать, что f (n) = не является Theta (2 ^ n), а вместо этого Theta (phi ^ n). Можем ли мы определить, после ввода какого размера (размера массива и/или значения изменения) алгоритм действительно является Theta(2^n)?   -  person Dominic Farolino    schedule 18.07.2016
comment
Я считаю, что нет ввода, для которого это Theta (2 ^ n), хотя он становится все ближе и ближе по мере увеличения количества монет. Я считаю (с некоторыми доказательствами, но без строгих доказательств), что сложность равна Theta(r^n), где r+r^(-|S|) = 2 и 1 ‹= r ‹ 2.   -  person Paul Hankin    schedule 18.07.2016
comment
Да, бит closer and closer - это то, о чем я тоже подумал.. спасибо   -  person Dominic Farolino    schedule 18.07.2016

Ответы (3)


arrow_upward
3
arrow_downward

Два фрагмента кода одинаковы, за исключением того, что второй использует рекурсию вместо цикла 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 (нм) и использует память O (n), и он чрезвычайно лаконичен - по размеру сравним с вашим наивным рекурсивным решением. https://stackoverflow.com/a/20743780/1400793. Он написан на Python, но легко конвертируется в C++.

person Paul Hankin    schedule 18.07.2016
comment
Большое спасибо. Да, я понимаю подходы DP к этой проблеме. Мне просто было просто интересно узнать, имеют ли рекурсивные версии одинаковую сложность, потому что я дошел до того, что убедил себя, что это может пойти в любом случае, ха-ха. - person Dominic Farolino; 18.07.2016
comment
Кстати, хорошее решение для py - person Dominic Farolino; 18.07.2016

arrow_upward
1
arrow_downward

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

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

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

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

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

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

person indjev99    schedule 18.07.2016
comment
Я прочитал всю статью. Мой вопрос касается рекурсивной части статьи, а не части DP. Я также понимаю часть статьи о DP, я просто был немного смущен тем, была ли моя рекурсивная версия такой же сложной, как их. Это был скорее вопрос общей сложности, чем что-либо еще. Спасибо! - person Dominic Farolino; 18.07.2016
comment
Понимаю. Я просто хотел убедиться, что вы поняли решение DP. В любом случае, мне удалось ответить на ваш вопрос, или мне нужно еще что-то объяснить? - person indjev99; 18.07.2016
comment
Нет, я думаю, вы прояснили мое замешательство. Я дошел до того, что мог видеть, что это алгоритм n ^ n, хотя он, казалось, выполнял тот же объем работы, что и решение, которое явно было 2 ^ n. Спасибо! - person Dominic Farolino; 18.07.2016

arrow_upward
0
arrow_downward

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

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,853075 с.
ИЗМЕНИТЬ
Я интерпретирую результат, поскольку временная сложность двух алгоритмов одинакова.

person FazeL    schedule 18.07.2016
comment
Не заставляйте меня начинать с того, как теоретическая сложность алгоритма выбрасывается из окна при практическом применении... Информация, представленная здесь, вероятно, устареет, и поэтому полезность, вероятно, уменьшится. Оставьте, если хотите, но я бы не был доволен этим как ответом на вопрос... Подумайте о том, что задает вопрос. - person autistic; 18.07.2016