是否有可能有两个有效的大 O 运行时依赖于不同的变量？
Is it possible to have two valid big O runtimes that depend on different variables?
考虑子集和问题，给定一组所有正整数，并希望确定使用其中的一个子集获得所需值的方法的数量。本质上，计算硬币零钱的解决方案数量，同时每种面额只有一枚硬币。该算法（取自此处：https://www.youtube.com/watch?v=nqlNzOcnCfs）计算如下：
作者将 运行 时间表示为 O(n * total)，其中 n 是您可以用来构成总和的整数个数（此处 n = 4），total 是您希望求和的值。
但是在最坏的情况下，递归最多可以在最后一个else语句中拆分两次，递归的深度最多为n，所以你不能也说递归树有一个最大调用次数 O(2^n) 这应该是另一个有效的 运行 时间复杂度？这个大O根本不依赖total，逻辑上有矛盾吗？
But in the worst case, the recursion can split at most twice in the last else statement and the depth of the recursion is at most n, so couldn't you also say that recursion tree has a maximum number of calls O(2^n)
如果不是实施顶部的这一行，情况就会是这样：
if key in mem:
return mem[key]
在 total 和 i 的相同组合的 return 值具有的情况下，正是这一行阻止代码进入最后一个 else被计算。最多有 n * total 个这样的组合，因此这是计算算法的大 O(...) 的限制因素。这种与动态规划相关的技术称为memoization. The timing you get in this situation is dependent on total, so the algorithm is pseudo-polynomial。
考虑子集和问题，给定一组所有正整数，并希望确定使用其中的一个子集获得所需值的方法的数量。本质上，计算硬币零钱的解决方案数量，同时每种面额只有一枚硬币。该算法（取自此处：https://www.youtube.com/watch?v=nqlNzOcnCfs）计算如下：
作者将 运行 时间表示为 O(n * total)，其中 n 是您可以用来构成总和的整数个数（此处 n = 4），total 是您希望求和的值。
但是在最坏的情况下，递归最多可以在最后一个else语句中拆分两次，递归的深度最多为n，所以你不能也说递归树有一个最大调用次数 O(2^n) 这应该是另一个有效的 运行 时间复杂度？这个大O根本不依赖total，逻辑上有矛盾吗？
But in the worst case, the recursion can split at most twice in the last else statement and the depth of the recursion is at most n, so couldn't you also say that recursion tree has a maximum number of calls O(2^n)
如果不是实施顶部的这一行，情况就会是这样：
if key in mem:
return mem[key]
在 total 和 i 的相同组合的 return 值具有的情况下，正是这一行阻止代码进入最后一个 else被计算。最多有 n * total 个这样的组合，因此这是计算算法的大 O(...) 的限制因素。这种与动态规划相关的技术称为memoization. The timing you get in this situation is dependent on total, so the algorithm is pseudo-polynomial。