c# - 递归 for 循环代码的时间复杂度

Question

我有这个代码，

void Generate(List<string> comb, string prefix, string remaining)
{
       int currentDigit = Int32.Parse(remaining.Substring(0, 1));

            if (remaining.Length == 1)
            {
                for (int i = 0; i < dictionary[currentDigit].Length; i++)
                {
                    comb.Add(prefix + dictionary[currentDigit][i]);
                }
            }
            else
            {
                for (int i = 0; i < dictionary[currentDigit].Length; i++)
                {
                    Generate(comb, prefix + dictionary[currentDigit][i], remaining.Substring(1));
                }
            }
}

上述代码的时间复杂度是多少？

它生成是 O(n) 并且它本身正在执行 n 次所以 O(n^2)？

字典是 len = 10 并且有电话键盘存储它。2 = "abc"等。

这段代码的初始调用会像

生成(新列表()，“”，“12345”);

谢谢。

Answer 1

假设字典大小为 m，输入字符串大小为 n(剩余)这将是:

T(1) = m + constant;
T(n) = m T(n-1) + O(n) ==> T(n) = O(m^n)

实际上每次运行else部分，你都会运行m次，O(n)的函数。