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バイトは約1GBに相当）の単語でうまくいくと思います。

しかし、時間の観点からすると、約100文字の単語は計算に数日かかる可能性があり、1000文字の単語は数か月から数年かかる可能性があると思います。いずれにせよ、16000文字の単語に対してこのアルゴリズムを実行すると、おそらくその終わりを確認することはできません。