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

Jiale Xue - MSFT 46,296 信誉分 Microsoft 供应商
2024-04-09T06:52:03.2066667+00:00

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

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

前任:

有效步数 = [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

.NET 运行时
.NET 运行时
.NET: 基于 .NET 软件框架的 Microsoft 技术。运行时: 运行未编译为机器语言的应用所需的环境。
54 个问题
0 个注释 无注释
{count} 票

接受的答案
  1. Hui Liu-MSFT 48,571 信誉分 Microsoft 供应商
    2024-04-09T08:16:44.9+00:00

    这种方法没有固定的时间复杂度。 假设 '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)之间。


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

    1 个人认为此答案很有帮助。
    0 个注释 无注释

0 个其他答案

排序依据: 非常有帮助

你的答案

问题作者可以将答案标记为“接受的答案”,这有助于用户了解已解决作者问题的答案。