计算深度极限递归算法的复杂度

Question

早上好，我正在学习递归调用时的算法和计算复杂度的方法，但是我找不到递归调用中的级别限制如何影响复杂度计算的参考。例如下面的代码:

   countFamilyMembers(int level,....,int count){
        if(noOperationCondition) { // for example no need to process this item because business rules like member already counted
            return count;
        } else if(level >= MAX_LEVEL) { // Level validation, we want just to look up to certain level
            return ++count //last level to see then no more recurrence.
        } else {
            for (...each memberRelatives...) {  //can be a database lookup for relatives to explore
                count = countFamilyMembers(++level,...,++count);
            }
            return count;
        }
    }

我认为这是O(2^n)因为循环中的递归调用。然而，我有两个主要问题:1. 如果循环值与原始输入完全不相关会发生什么?这也可以被认为是n吗?2. 级别验证肯定会限制递归调用，这对复杂性计算有何影响?

Answer 1

谢谢你的说明。所以我们将n作为亲戚数量的"最佳度量";这在某些范例中也被称为"扇形向外"。

因此，0级有1个人，1级有n， 2级有n^2，以此类推。对回报值的粗略估计……操作次数(节点访问，增量等)是n^level在0到MAX_LEVEL级别范围内的和。优势项是最高指数n^MAX_LEVEL 根据给定的信息，我相信这就是你的答案:O(n^^MAX_LEVEL)，也就是多项式时间。

注意，如果你碰巧得到了n的值，甚至是n的上界，那么它就变成了一个常数，复杂度为O(1)。