循环内有 2 个参数的递归 时间复杂度

Question

我试图找到这个递归函数的时间复杂度，我该如何解决这个问题？

假设输入是正数，有效步骤是唯一列表

前任：

有效步数 = [1,2] 距离 = 3

有效步数 = [1,2,3] 距离 = 4

int countpaths(int[] validsteps, int distance)
    {
        if (distance == 0)
        {
            return 1;
        }

        int paths = 0; 

        foreach (int step in validsteps)
        {
            if (distance >= step)
            {
                paths += countpaths(validsteps, distance - step);
            }

        }

        return paths;
    }

Note：此问题总结整理于: Recursion with 2 arguments inside a loop Time Complexity

Answer 1

这种方法没有固定的时间复杂度。 假设 'validsteps' 的长度为 N，'distance' 的值为 k。 在最佳情况下，时间复杂度为 O（1）：

K <= Min(validsteps)  

例如：

validsteps = [2,3,4] distance = 1  

在最坏情况下，时间复杂度为 O（ K 的 2 次方） ： O（2 k )

K = Max(validsteps) validsteps = [1,2,3,...,N]  

例如：

validsteps = [1,2,3,4] distance = 4  

通常，时间复杂度的范围在 O（1） 和 O（K 次幂 2）之间。

---

如果答案有帮助，请点击“接受答案”并点赞。 注意：如果您想接收此线程的相关电子邮件通知，请按照我们文档中的步骤启用电子邮件通知。