Возможно ли иметь два действительных времени выполнения больших O, которые зависят от разных переменных?

Question

Рассмотрим проблему суммы подмножеств, где вам дан набор всех положительных целых чисел, и вы хотите определить количество способов, которыми вы могли бы использовать их подмножество для получения желаемого значения.По сути, подсчет количества решений для изменения монеты при наличии только одной монеты каждого номинала.Этот алгоритм (взятый отсюда: https://www.youtube.com/watch?v=nqlNzOcnCfs) вычисляет это:

Автор представил время выполнения как O(n * total), где n - это число целых чисел, которое вы можете использовать, чтобы составить сумму (здесь n = 4), а total - это значение, к которому вы хотите суммировать.

Но в худшем случае рекурсия может делиться максимум дваждыв последнем операторе else глубина рекурсии не превышает n, поэтому нельзя ли также сказать, что в дереве рекурсии максимальное количество вызовов O(2^n), и это должно быть еще одной допустимой сложностью во время выполнения?противоречие здесь, так как этот большой O вообще не зависит от total?

Answer 1

Но в худшем случае рекурсия может делиться не более двух раз в последнем операторе else, а глубина рекурсии не более n, поэтому нельзя также сказать, что дерево рекурсии имеет максимальное числовызывает O (2 ^ n)

Это было бы так, если бы не эта строка в верхней части реализации:

if key in mem:
    return mem[key]

Именно эта строкапредотвращает переход кода в этот последний else в тех случаях, когда было вычислено возвращаемое значение для той же комбинации total и i.Существует не более n * total таких комбинаций, что является ограничивающим фактором для вычисления больших O (...) для алгоритма.Этот метод, связанный с динамическим программированием, называется памятка .Время, которое вы получаете в этой ситуации, зависит от total, поэтому алгоритм равен псевдополином .