O (n) ??? Quelqu'un peut-il me dire le grand O de. Reverse

-2

dire que j'utilise les méthodes suivantes pour rechercher un palindrome. Je sais que le premier est O (n) parce qu'il passe par une chaîne entière. Est-ce que le .reverse() dans le StringBuffer fait aussi O (n)? Je ne suis pas inquiet de trouver une meilleure façon de résoudre le problème Im essayant de comprendre si la méthode inverse inverse physiquement la chaîne ou est-ce beaucoup plus efficace que cela ?? MerciO (n) ??? Quelqu'un peut-il me dire le grand O de. Reverse

public static boolean isAPalindrome(String s1){ 

    String tmp = "";  
    int length = s1.length(); 
    for(int i = 0; i < s1.length(); i++){   
     tmp += s1.charAt(s1.length()-i-1); 
    }  
    if (s1.equals(tmp)) return true; 
    return false;   

} 

public static boolean isAPalindrome(String s1){ 

    StringBuffer a = new StringBuffer(s1); 
    return s1.equals(a.reverse().toString()); 

}

Source

2016-01-20 Matthew Leighty

http://stackoverflow.com/questions/2439141/what-is-the-most-efficient-algorithm-for-reversing-a-string-in-java – novice

Salut Matthew, si une réponse a résolu votre question, veuillez accepter en cliquant sur la coche verte à côté de lui. Merci – Idos

Inverser une chaîne ne peut pas être plus rapide que O(n) (sous représentation normale d'une chaîne).
Vous devez "opérer" sur chaque caractère de la chaîne, donc il ne peut pas théoriquement être plus rapide que cela.

StringBuffer étend AbstractStringBuilder qui implémente reverse. Vous pouvez regarder le code source vous-même here.

Note: ceci est pas dire que StringBuilder/s Bufferreverse se déroulera aussi vite comme méthode O(n)reverse que vous allez écrire. Il va probablement exécuter beaucoup plus rapidement. Mais asymptotiquement il sera toujours O(n).

Source

2016-01-20 19:02:45 Idos

Ceci, si vous inversez un problème qui doit vérifier soit la solution ou quelque chose est juste le même et pas mieux. Juste une solution différente sans avantage héritier. – jgr208

Ce n'est simplement pas vrai. Vous pouvez très bien avoir une structure de données pour les chaînes avec une opération inverse à temps constant. –

@ EmilVikström soin d'élaborer? L'OP n'a évidemment pas posé de questions sur des représentations obscures de Strings. Tout "normal" nécessiterait O (n) à tout le moins. – Idos

Vous pouvez implémenter un reverse qui est effectivement o (1), mais pas avec les classes de chaînes typiques: Vous pouvez le faire en implémentant une classe de chaînes avec un membre de direction, qui peut prendre les valeurs "forward" ou "backward" ". Mais cela n'aurait de sens que si le retour domine votre performance sur tous les autres calculs.

Source

2016-01-20 19:21:14

O (n) ??? Quelqu'un peut-il me dire le grand O de. Reverse

Répondre

Questions connexes