手机键盘数字转字母递归算法的时间复杂度求解

首先，我们先确认你的递推关系式是准确的：你给出的 T(n) = T(n-1) + k^(n-1) * k 可以简化为 T(n) = T(n-1) + k^n，其中：

• n 是输入的数字个数
• k 是单个数字映射的最多字符数（这里k=4，对应数字7和9的4个字母）

递推式求解过程 #

我们从初始条件开始逐步展开递推：

1. 初始条件：当n=0（输入为空字符串），算法直接返回空列表，时间复杂度 T(0) = O(1)
2. 展开递推链：

   T(n) = T(n-1) + k^n
   T(n-1) = T(n-2) + k^(n-1)
   T(n-2) = T(n-3) + k^(n-2)
   ...
   T(1) = T(0) + k^1
   

3. 累加消项：将所有式子相加，左右两边的T(n-1)、T(n-2)...T(1)会相互抵消，得到：

   T(n) = T(0) + k^1 + k^2 + ... + k^n
   

4. 等比数列求和：上面的求和式是首项为k、公比为k的等比数列，求和公式为 k*(k^n - 1)/(k-1)。当k>=2时，这个式子的主导项是k^n，而T(0)=O(1)是常数项，可以忽略。因此最终的时间复杂度是 O(k^n)。

结合代码验证 #

看你提供的递归代码：

class Solution { 
    public List<String> letterCombinations(String digits) { 
        if(digits == null || digits.length() == 0) { 
            return Collections.emptyList(); 
        } 
        Map<Integer, List<Character>> map = new HashMap<>(); 
        map.put(2, Arrays.asList('a','b','c')); 
        map.put(3, Arrays.asList('d','e','f')); 
        map.put(4, Arrays.asList('g','h','i')); 
        map.put(5, Arrays.asList('j','k','l')); 
        map.put(6, Arrays.asList('m','n','o')); 
        map.put(7, Arrays.asList('p','q','r','s')); 
        map.put(8, Arrays.asList('t','u','v')); 
        map.put(9, Arrays.asList('w','x','y','z')); 
        List<String> result = new ArrayList<>(); 
        recurse(digits, result,"", map, 0); 
        return result; 
    } 
    public void recurse(String digits, List<String> result, String temp, Map<Integer, List<Character>> map, int index) { 
        if(index == digits.length()) { 
            result.add(temp); 
        } else { 
            Integer ch = Character.getNumericValue(digits.charAt(index)); 
            List<Character> chars = map.get(ch); 
            for(int i=0; i < chars.size(); i++) { 
                recurse(digits, result, temp + chars.get(i), map, index + 1); 
            } 
        } 
    } 
}

递归函数recurse在处理第index个数字时，会遍历当前数字对应的所有字符，每个字符都会触发一次针对index+1的递归调用。当处理到第n个数字时，前面已经生成了k^(n-1)个组合（假设每个数字都对应最多k个字符），每个组合都要和当前的k个字符拼接，这一步的操作数就是k^(n-1)*k = k^n，正好对应递推式中的k^n项。而T(n-1)则是处理前n-1个数字的时间开销，所以递推式完全符合代码的执行逻辑。

另外补充一点：实际的组合总数是各个数字对应字符数的乘积（比如输入"23"时是3*3=9个组合），O(k^n)是这个算法时间复杂度的上界，因为我们用了最大的字符数k来计算，实际运行时间会和生成的组合总数成正比，也就是O(M)，其中M是最终的组合数量。

内容的提问来源于stack exchange，提问作者Sanket