我得到了一个程序，它分别依赖于大小为m和n的两个条目。如果T（m，n）是问题的运行时间，则如下所示：
t（m，n）=t（m-1，n-1）+t（m-1，n）+t（m，n-1）+c
对于给定的常数C。
我可以证明时间复杂度是ω（2 ^ min（m，n））。然而，它似乎是复杂的Ω（2 ^ max（m，n））（它刚刚被确认给我），但我找不到正式的证明。有人有把戏吗？
提前谢谢！
最佳答案
从我的头顶：
我假设T（m，n）的递归在达到T（0，x）或T（x，0）时停止。
你有3个因素促成了复杂性：
系数1:t（m-1，n-1）同时减小m和n，因此m或n变为0之前的长度为min（m，n）步（见下面的注释）
因子2:T（m-1，n）只会减少m，所以m=0之前的长度是m步。
系数3:t（m，n-1）与上述相同，但直到n=0为n步。
总体复杂度是所有复杂性的最大值，因此它必须与最大值相关。
max( min(m,n) steps, m steps, n steps) = max(m,n)
rather than min(m,n).
我想你可以填一下细节常数C没有贡献，或者更精确地贡献于O（1），这是这里所有复杂度中最低的。
注意项目1：这个因子还有一个分支m-1直到0和n-1直到0，严格来说，它的复杂性也将是max（m，n）。
关于algorithm - 程序的指数复杂度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21858039/