Un outil pour le calcul de la big-O moment de la complexité du code Java?
J'ai une question concernant le temps de la complexité (big O notation) du logiciel Java. Est-il un moyen de calculer rapidement ou de le tester (ou de tout site web qui pourrait le calculer pour moi serait la bienvenue). Par exemple je voudrais vérifier pour l'extrait de code suivant et, éventuellement, d'améliorer ainsi:
int dcount = 24423567;
int a = 0;
if (dcount == 0){
a = 1;
}
String ds = Integer.toString(dcount);
String[] sa = ds.split("(?<=.)");
HashSet hs = new HashSet();
Collections.addAll(hs, sa);
a = hs.size();
if (dcount < 0)
a--;
System.out.println(a);
"Le temps de la Complexité" signifie généralement le cas le pire moment de la complexité. Ce problème a été révélé impossible.
Je voulais dire (big-O) de la complexité. Allons éditer le post.
Si vous voulez compter distinctes des chiffres dans un nombre, que le code n'est certainement pas une solution optimale à la fois dans le temps et dans l'espace.
comment feriez-vous pour améliorer Philipp? Quels sont les lieux qui doivent être corrigées?
aussi, l'intention sera de plus en plus évidents(!)
Je voulais dire (big-O) de la complexité. Allons éditer le post.
Si vous voulez compter distinctes des chiffres dans un nombre, que le code n'est certainement pas une solution optimale à la fois dans le temps et dans l'espace.
comment feriez-vous pour améliorer Philipp? Quels sont les lieux qui doivent être corrigées?
aussi, l'intention sera de plus en plus évidents(!)
OriginalL'auteur aretai | 2012-03-31
Vous devez vous connecter pour publier un commentaire.
@Emory l'a souligné, il est prouvable impossible de déterminer le big-O moment de la complexité de l'arbitraire d'un morceau de code automatiquement (la preuve en est une réduction de la Problème De L'Arrêt). Cependant, il existe des outils qui peuvent tenter de mesurer la complexité d'un morceau de code de façon empirique, en l'exécutant sur plusieurs entrées différentes. Un tel outil est décrite dans le document “la Mesure Empirique de la Complexité de Calcul” en Goldsmith, Aiken, et Wilkerson. Il fonctionne en essayant de faire une régression sur le programme d'exécution en fonction de sa taille. L'outil, appelé tendance-prof, est disponible en ligne.
Espérons que cette aide!
L'outil fait beaucoup plus que de simplement exécuter le programme. Il ajoute beaucoup de binaire de l'instrumentation pour la mesure individuelle des fonctions / blocs de code, et il est certainement beaucoup plus facile que de le faire à la main. En principe, on pourrait faire la même chose manuellement, mais il serait bien plus difficile.
il est toujours bénéfique si vous fournissez le nom de la feuille de papier et pas seulement "dans ce livre" comme des liens cassé assez souvent.
Grand point. Fixe!
OriginalL'auteur templatetypedef
J'ai peut-être la résolution quelqu'un à faire leurs devoirs, mais la question a été la mendicité pour un sane solution...
Comptage distinct des chiffres dans un nombre nécessite pas de chaînes, des ensembles ou des expressions régulières, juste une simple arithmétique.
La méthode suivante s'exécute en O(n) temps (n = nombre de chiffres dans l'entrée) et de la constante de l'espace:
Faire ce travail pour les nombres négatifs est laissé comme exercice au lecteur 😉
J'espère que vous vous trouvez cette goutte de code utile 🙂
oui c'est une solution élégante ainsi merci. Bien qu'il n'a pas directement répondu à ma question (comme celle ci-dessus), mais 1 upvote vous avez.
Je crains que votre solution n'est pas soigné comme je le pensais essayer de vérifier cette 000121212 comme entrée, il va produire une valeur de 4. Mon code ne réussit pas ce test.
0121212
est interprétée comme un nombre octal (zéro) et est41610
comme un nombre décimal et donc 4 est correcte.OriginalL'auteur Philipp Reichart