algorithm - 如果我有 1GB 内存，我可以在我的字符串排列算法中支持的最大字符串大小是多少

Question

对于下面提到的字符串排列算法或任何其他递归算法，如果我有 1 GB 的专用内存可用，则支持的最大字符串大小是多少。

public void permutate(String prefix, String word){

    if(word.length() <= 1){
        System.out.println(prefix + word);
    } else{
        for (int i = 0; i < word.length(); i++) {
            String temp = word.substring(0,i) + word.substring(i+1);
            permutate(prefix + word.charAt(i), temp);
        }
    }
}

public void permutate(String word){
    permutate("", word);
}

Answer 1

那么你的内存复杂度 O(N^2) （N 是单词的长度）所以对于 1 GB，我会说你可以用大约 16000 个字符的单词（16000^2 * 4 字节大约等于 1 GB）做得很好。

然而，从时间的角度来看，一个大约 100 个字符的单词可能需要几天的时间来计算，而我认为一个 1000 个字符的单词可能需要几个月甚至几年的时间。在任何情况下，如果你对一个有 16000 个字符的单词运行这个算法，你可能永远看不到它的结尾。