ceea ce este dimensiunea maximă a șir i poate sprijini în permutations șir meu algo dacă am memorie de 1 GB

pentru algo-ul permutare de șir mai jos sau orice algo recursiv, care este dimensiunea maximă a șirului acceptat dacă am 1 GB de memorie dedicată disponibilă.

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);
}
0

1 răspunsuri

Well your memory complexity O(N^2) (N being the length of the word) so for 1 GB I would say you could do well with a word of about 16000 characters (16000^2 * 4 bytes equals roughly 1 GB).

However from time point of view a word of about 100 characters could take days to compute, and a word of 1000 chars could take months even years I think. In any case if you run this algorithm for a word with 16000 characters you'll probably never get to see the end of it.

0
adăugat
Sunteți oprit de mai multe ordini de mărime: când algoritmii O (N!) sunt luați în considerare, "numărul magic" este 12: se pot potrivi operațiile primitive 12! în o secundă. 20! durează aproximativ un an; 22! durează 400 de ani. O etapă a acestui algoritm necesită operații primitive de 50 ... 100 plus o operație I/O care este de 1000 de ori mai lentă. Prin urmare, un șir de lungime de 15 ar păstra un calculator mediu ocupat pentru un an sau cam asa ceva; un șir de 16 caractere îl va păstra ocupat până când va fi gata să fie aruncat.
adăugat autor dasblinkenlight, sursa