Temps complexité O () de isPalindrome ()

StackOverflow https://stackoverflow.com/questions/1318545

Question

J'ai cette méthode, isPalindrome (), et je suis en train de trouver la complexité du temps de celui-ci, et aussi réécrire le code de manière plus efficace. 

boolean isPalindrome(String s) {
    boolean bP = true;
    for(int i=0; i<s.length(); i++) {
        if(s.charAt(i) != s.charAt(s.length()-i-1)) {
            bP = false;
        }
    }
    return bP;
}

Maintenant, je sais que ce code vérifie les caractères de la chaîne pour voir si elle est la même que celle qui la précède et si elle est alors ça ne change pas bP.

Et je pense que je sais que les opérations sont s.length (), s.charAt (i) et s.charAt (s.length () - i -).)

Faire l'O complexité temporelle (N + 3), je pense? Ce correcte, sinon ce qui est et comment est-ce compris.

Aussi le rendre plus efficace, serait-il bon de stocker le caractère dans les chaînes temporaires?

Était-ce utile?

La solution

Le code donné semble être vérifier si une chaîne est un palindrome en vérifiant si le caractère « N » est la même chose que « longueur N ». Comme déjà mentionné, vous pouvez augmenter l'efficacité par

  • uniquement vérifier la première moitié
  • sortir (return false) dès que vous trouvez une non-correspondance

Pour ces suggestions, j'ajouter

  • ne recalcule pas s.length () à plusieurs reprises chaque fois à travers la boucle, car elle ne change pas.

Compte tenu de tout cela: 

boolean isP(String s) {
  int l = s.length();
  int l2 = l/2;
  int j = l - 1;
  for(int i=0; i<l2; i++) {
    if(s.charAt(i) != s.charAt(j)) {
        return false;
    }
    j--;
  }
  return true;
}

Autres conseils

Il est juste O (N).

Dire O (N + 3) ne sont pas vraiment significatifs -. Facteurs constants sont ignorés

Vous pouvez le rendre plus rapide en brisant quand il trouve une différence: 

bP = false;
break;

(Non pas que cela change le fait que ce soit O (N), mais il accélérer dans la plupart des cas.)

Ce n'est pas vrai:

  

ce code vérifie les caractères de la chaîne pour voir si elle est la même que celle qui la précède

Il vérifie que les caractères au début correspondent à ceux à la fin, il est donc naïf palindrome vérificateur.

Une autre serait à speedup boucle jusqu'à s.length()/2 -. Sinon vous faites toutes les comparaisons deux fois pour une chaîne qui est un palindrome

Ceci est probablement la mise en œuvre la plus efficace en Java: 

    public static boolean isP(String s) {
        char[] chars = s.toCharArray();
        for (int i = 0; i < (chars.length / 2); i++) {
            if (chars[i] != chars[(chars.length - i - 1)])
                return false;
        }
        return true;
    }

Avantages:

  • retour à première vue de la différence.
  • Utilise un accès direct char [] pour éviter les contrôles effectués dans aboundary charAt
  • Seulement la moitié Itère la chaîne, par opposition à la chaîne complète.

Il est, comme toutes les autres solutions proposées, toujours O (N).

Je viens de mesurer les temps fo les solutions présentées pour une chaîne vraiment grand (fois nanosecondes): 

 Aran:           32244042
 Andreas:        60787894
 Paul Tomblin:   18387532

D'abord, les mesures ci-dessus ont été effectuées avec le client VM . Ainsi, le i < (chars.length / 2) de calcul n'a pas été inline comme une constante. Le paramètre -server Vm a donné un meilleur résultat: 

 Aran:           18756295
 Andreas:        15048560
 Paul Tomblin:   17187100

Pour conduire un peu extrême:

Un mot d'avertissement d'abord:. NE PAS UTILISER CE CODE DANS UN PROGRAMME que vous souhaitez utiliser / SHIP

Il contient des bugs cachés et ne respecte pas le Java et a l'erreur ne gère pas, comme l'a souligné dans les commentaires. Il sert uniquement à démontrer les améliorations des performances théoriques pouvant être obtenus par des tours sales.

Il y a certains frais généraux lors de la copie du tableau de la chaîne, parce que la classe chaîne fait en interne une copie défensive.

Si on obtient le charbon d'origine [] de la chaîne directement, nous pouvons faire sortir un peu de performance, au coût d'utilisation et la réflexion des opérations sur unsave la chaîne. Cela nous obtient une performance de 20%. 

public static boolean isPReflect(String s) {
    char[] chars = null;
    try {
        final Field f = s.getClass().getDeclaredField("value");
        f.setAccessible(true);
        chars = (char[]) f.get(s);
    }
    catch (IllegalAccessException e) {
    }
    catch (NoSuchFieldException e) {
    }

    final int lenToMiddle = chars.length / 2;
    for (int i = 0; i < lenToMiddle; i++) {
        if (chars[i] != chars[(chars.length - i - 1)]) 
            return false;
    }
    return true;
}

Temps: 

 Aran:           18756295
 Andreas1:       15048560
 Andreas2:       12094554
 Paul Tomblin:   17187100

Il est O (N). Vous faites des comparaisons de N, où N = s.length (). Chaque comparaison prend O (1) fois, comme il est d'une seule comparaison de caractères.

3 n'a pas d'importance, comme la notation asymptotique ne se préoccupe que le terme d'ordre le plus élevé.

Voici une autre solution avec deux pointeurs opposés: 

boolean isPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j && s.charAt(i) == s.charAt(j)) {
        ++i;
        --j;
    }
    return i >= j;
}

La complexité est à nouveau O ( n ).

Pour aller un peu plus dans les détails: Disons que tous les coûts de fonctionnement 1 unité. Les comparaisons, les affectations, les opérations arithmétiques, fonction appelle chaque unité coût 1. Ainsi, un appel de coûts de isPalindrome au pire des cas (s est un palindrome) prend par exemple: 

  4 + n/2 · (3 + 4) + 1
= 5 + n/2 · 7
= 5 + 7/2 · n

Et puisque le facteur constant (ici 5 + 7/2) est omis, nous nous retrouvons avec 5 + 7/2 · n ∈ O ( n ).

D'abord, il ne peut pas être une solution simple fil pour ce problème où le « pire des cas » complexité est mieux que O(N) pour les chaînes d'entrée arbitraires. En termes simples, tout algorithme doit examiner tous les caractères de la chaîne dans le pire des cas. En théorie, vous pouvez améliorer O(N) en utilisant le parallélisme matériel; à-dire avoir un nombre infini évolutive de processeurs travaillant sur les différentes parties de la chaîne. Dans la pratique, il serait difficile d'atteindre une vitesse du tout. Le coût de l'envoi de la chaîne d'entrée (ou parties pertinentes) à chaque processeur va être « O (N) », à moins d'une solution que je ne sais pas.

Deuxièmement, comme vous pouvez voir le comportement de O(N) n'est pas la réponse finale. Vous devez également considérer la constante multiplicatif comme N -.> L'infini, et les termes moins pour les petites valeurs de N

Troisièmement, @dfa dit que ce n'est pas votre entreprise à micro-optimize. Il est sur la bonne voie, mais je ne pense pas que ce soit coupé tout aussi clair que cela. OMI, il est une perte de temps micro-optimisation à moins 1) votre application vraiment a besoin de courir aussi vite que possible, et 2) votre profil de l'application montre que ce calcul particulier vraiment est un goulot d'étranglement important.

Enfin, un micro-optimisation qui rend un programme plus rapide pour un compilateur particulier plate-forme / JIT matériel, peut le rendre plus lent pour l'autre. Code de micro-complexe optimisé est plus difficile pour un compilateur juste à temps pour générer un code efficace pour. Et si vous utilisez la réflexion pour accéder aux composants internes de (par exemple) la classe String, votre code pourrait en fait échouer sur certaines plates-formes. (Rien dans la spécification Java Class Library dit qu'une chaîne a un champ privé appelé « valeur » qui est un char[] !!!)

Alors tout d'abord, quelle est la méthode censé faire?

Je pense: déterminer si une chaîne est un palindrome

.

Bien évidemment, vous ne serez pas en mesure de le faire descendre sous O (N): 

O(N+3) == O(N)

L'autre question est, est-il la solution la plus efficace? Peut-être pas.

amélioration:

  1. Couper en deux. Vous vérifiez tous les caractères deux fois (comme Michiel Buddingh suggéré).

  2. Obtenir le tableau de caractères au préalable. Cela vous évite certains contrôles d'index qui se produisent à l'intérieur chatAt().

Toutes les autres opérations, charAt() et length(), sont O (1) avec la mise en œuvre standard de chaîne.

Première amélioration: vous pouvez briser une fois que vous trouverez un non-appariement, droit

En supposant que les opérations dans votre boucle peut être exécutée en temps constant, la complexité est O (N). Étant donné que la croissance des mesures de notation « Big-O », et non la vitesse pure, les facteurs constants peuvent être ignorées. Cela nous laisse la conclusion que O (N + 3) est égale à O (N).

Vous pouvez couper la complexité de la fonction dans la moitié en arrêtant à (i == (s.length () / 2) + 1). Il n'est pas pertinent en termes Big O, mais il est encore un gain assez décent.

Ou vous pouvez tout simplement faire 

def isPalindrome?(x)
 return x == x.reverse
end

Ceci est encore O (n) la complexité du temps.

Non affilié à StackOverflow
scroll top