电话号码字母组合的时间复杂度

Question

以下是LeetCode问题17：

给定一个包含2-9 (含2-9)数字的字符串，返回该数字可以表示的所有可能的字母组合。以任意顺序返回答案。

(https://leetcode.com/problems/letter-combinations-of-a-phone-number/)

下面是我的DFS递归代码：

class Solution {
    public static final String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
    public List<String> letterCombinations(String digits){
        List<String> result = new ArrayList<String>();
        if(digits == null || digits.length() == 0){return result;}
        
        
    
        int curr_index = 0;
        StringBuilder prefix = new StringBuilder("");
        
        update_result(digits, prefix, curr_index, result);
    
        return result;
        
    
    }

    private void update_result(String digits, StringBuilder prefix, int curr_index, List<String> result){
        if(curr_index >= digits.length()){
            result.add(prefix.toString());
            return;
        }
        else{
            String letters = map[ digits.charAt(curr_index) - '0' ];
            for(int i = 0; i < letters.length(); i++){
                prefix.append( letters.charAt(i) );
                update_result(digits, prefix, curr_index+1, result);
                prefix.deleteCharAt(prefix.length() -1);
            }
            return;
        }
        
    }

}

在LeetCode解决方案中，它表示时间复杂度为O(n*n^4)，其中n是输入的长度。除了n^4之外，我很难理解，剩余的额外n来自哪里。

我对代码的分析是: T(n) = O(1) + 4T(n-1)。( for循环重复4次，长度减去1。在循环中，更新前缀字符串需要恒定的时间。)

它求解为1+4+ 4^1+ ... + 4^n = O(4^n)

有人能解释为什么解决方案说时间复杂度是O(n*4^n)吗？

Answer 1

我同意你的观点，时间复杂度应该是O(4^n)。

我有几个想法，为什么它可以是O(n * 4^n)：

当

1. StringBuilder's追加方法的容量达到阈值时，它需要O(n)时间，这意味着将所有元素复制到新的数组中。但是在您的例子中，结果字符串的最大长度是4(根据问题约束)，而阈值的默认值是16 (https://docs.oracle.com/javase/8/docs/api/java/lang/StringBuilder.html#StringBuilder-java.lang.String-)。由于4< 16，所以总是需要O(1)时间。

由于数组拷贝，

1. StringBuilder's deleteCharAt方法在最坏的情况下需要O(n)时间。但在您的示例中，您只删除了最后一个字符，这需要O(1)时间。

1. 使用字符串而不是StringBuilder，其中连接和删除一个元素需要O(n)时间