Convertit une chaîne en nombre & vice versa complexité

Quelle serait la complexité de la conversion d'une corde à son nombre équivalent ou vice-versa? Faut-il changer en fonction du langage de programmation?

Sur le visage de celui-ci, on doit parcourir l'ensemble de la chaîne à convertir en nombre, de sorte qu'il est O(n), ou un certain typecasting utilisé?

Ce doute est venu à propos, quand j'ai écrit une routine pour vérifier si un nombre donné est un palindrome ou non. Une approche pourrait être de continuer à diviser le nombre par la base (ici 10), d'accumuler des chiffres, et de les mettre ensemble à la fin. Exemple: 309/10=rem(9), 30/10=rem(0), 3/10=rem(3). nous obtenons 903.

Une autre approche que j'ai adoptée a été de convertir ce nombre en chaîne de caractères, et depuis les chaînes ont des charges de fonctions de membre de split, reverse, etc., le code a été beaucoup plus courte et plus propre, mais est-ce la meilleure façon de le faire?

Que voyez-vous comme "N" dans votre cas?
il n'y a pas de limite sur la taille de N...
OK, je vais la poser différemment: Suis-je en droit de supposer que vous voyez N la longueur de la chaîne d'entrée et de demander la algorithmical de la complexité de l'analyse de cette chaîne en un nombre?
oui ttoni, vous avez raison...

OriginalL'auteur Srikar Appalaraju | 2010-12-19

  1. 13

    Les chaînes numériques sont des nombres mis en forme dans la notation de position - de sorte que la valeur de chaque chiffre multiplié par une puissance de la base doit être pris en compte afin de convertir le nombre en format binaire.

    Donc oui, c'est un O(N), parce que le temps d'exécution augmente de façon linéaire comme de plus en plus les chiffres sont ajoutés. Cependant, dans la pratique, N peut être limité par ce que des données numériques-types de la langue prend en charge (par exemple, int32_t, int64_t). Mais si la précision arbitraire nombre de types sont utilisés (dont certaines langues, comme le Python, l'utilisation par défaut), puis il n'y a pas de limite au nombre de chiffres (autres que la mémoire disponible, évidemment).

    OriginalL'auteur Charles Salvia

  2. 4

    Pour convertir un nombre, vous devez toujours lire tous les chiffres. Il est donc au moins O(n).

    En train de faire quelque chose comme (pseudo-code)

    a = 0
foreach digit in string
do
   a = 10 * a + digit
end

    Est O(n). Si la complexité est O(n)

    strictement parlant, c'est mal. pour O(n) notation, n doit tendre vers l'infini.
    N tend vers l'infini si la précision arbitraire nombres sont utilisés.
    vous êtes de droite. Donc, cela n'a de sens que pour les langues avec construit-dans les nombres en précision arbitraire (ce qui exclut les C/C++ et C#).
    et @Vlad: mais pour en précision arbitraire cela devient O(n^2) depuis le calcul de la multiplication 10*a est O(n) opérations.
    l'OP parle de la intégré dans les conversions. Le haut-conversions ne peuvent pas travailler avec des non-construit-dans les types de. 😛

    OriginalL'auteur Peter van der Heijden

  3. 0

    Si vous êtes à la conversion d'un nombre N d'une chaîne de caractères. Il prend O(log(N)) avec la base 10. (Si vous divisez par 10 et de garder le reste)
    Si vous êtes à la conversion d'une chaîne de longueur N, alors elle prend O(N). (Si vous utilisez l'algorithme qui ne cesse d'ajouter à votre numéro de 10^(N)*chiffres(N))

    Si vous utilisez des fonctions qui ne sont pas les vôtres (disons par chaîne), vous ne pouvez attendre à être plus lent.

    À la fois prendre en O(N) où N est le nombre de chiffres. Ce est la bonne façon d'analyser les algorithmes de calcul.
    Si le nombre est N=10^5. Combien d'étapes pour convertir une chaîne de caractères? Je pense que O(log(N)), parce que c'est le nombre de chiffres.

    OriginalL'auteur synepis

  4. 0

    Je suis raisonnablement certain que le fait de traiter avec de la pure opérateurs numériques (en c++ et c# je pense qu'il serait le "%" opérateur de modulo) va être plus efficace si le code est correctement parce qu'à un certain niveau, vous avez à vérifier des caractéristiques similaires (la fin du match au début) et d'effectuer une conversion entre la chaîne et le nombre ne peut ajouter à la complexité de l'opération, si vous pouvez faire la même chose sans effectuer cette conversion.

    Cela dit, je ne voudrais pas vous soucier de l'impact sur les performances de conversion entre les nombres et les chaînes parce que c'est probablement insignifiant par rapport à l'impact sur les performances de la plupart des autres domaines du programme. Les types numériques sont limitées à 64 bits, ce qui met un niveau relativement bas de plafond sur le nombre de chiffres que vous pouvez planifier pour analyser de toute façon, sauf si vous êtes à la mise en place, à l'aide personnalisée codée en grand nombre types.

    Vous n'avez pas à vous soucier de la complexité de l'être O(n) où n est l'importance du nombre. Il serait plus comme O(n) où n est le nombre de chiffres (qui a le plafond aussi bas je l'ai mentionné), ou (comme mentionné dans une autre réponse) O(log(n)) si n est l'importance du nombre. Relativement faible impact sur les performances.

    Maintenant, si, comme vous le suggérez, vous n'avez aucune limite sur N (qui n'est pas possible parce qu'avec 2 GO de RAM, vous pouvez stocker uniquement les numéros avec jusqu'à 2 milliards de chiffres), alors nous pourrions avoir à réfléchir sur la performance de l'exécution d'opérateurs mathématiques. Considérer que la performance de l' "%" et l'opérateur "/" sur ce nombre important, type de. Mais alors se rendre compte que, pour convertir le nombre en une chaîne de caractères, c'est essentiellement à l'aide de ces mêmes opérateurs de toute façon. Encore une fois, vous ne pouvez pas battre le traiter comme un numéro directement si vous le faites à droite.

    OriginalL'auteur BlueMonkMN

  5. 0

    C# et en C/C++ n'ont pas spécial d'information dans les chaînes de caractères qui représente la (possible) valeur numérique. Par conséquent, ils ont besoin pour analyser la chaîne digit par digit lors de la conversion.

    Cependant, le nombre de caractères est limité, donc nous avons juste O(1): le temps de conversion est limitée (généralement par la conversion du plus grand nombre). Pour un int 32-bits, la conversion doit considérer maximum de 10 chiffres décimaux (et peut-être un signe).

    Conversion de chaîne de caractères est en fait en O(1), car lors de l'analyse, il suffit de ne considérer qu'un délimitée nombre de caractères (10+1 dans le cas de 32 bits de type int).

    Strictement parlant, on ne peut pas utiliser O-notation pour le cas de l'int-à-conversion de chaîne de caractères, puisque la valeur maximale de l'int est bornée. De toute façon, le temps nécessaire à la conversion (dans les deux sens) est limitée par une constante.

    @Charles suggère, d'autres langages (Python) peut effectivement utiliser des nombres en précision arbitraire. Pour l'analyse de ces numéros, le temps est O(number of digits), qui O(string length) et O(log(number)) pour les deux conversions, respectivement. Avec des nombres en précision arbitraire, on ne peut pas faire plus vite, puisque, pour les deux conversions tous les chiffres doivent être considérés. Pour les conversions vers/à partir d'un nombre limité la précision des nombres, de la même O(1) raisonnement s'applique. Cependant, je n'ai pas le profil de l'analyse en Python moi-même, donc peut-être moins efficace algorithme est utilisé.

    EDIT: suite à la @Steve suggestion, j'ai vérifié que l'analyse en C/C++ et C# ignore l'initiale de l'espace, de sorte que le temps pour la chaîne->int conversion est en fait O(input length). Dans le cas où il est connu que la chaîne est coupée, la conversion est de nouveau O(1).

    Bien sûr, nous pouvons utiliser la notation grand O, nous avons juste obtenir O(1) lorsque vous n'utilisez pas bigints.
    Je suis parler explicitement des C/C++ et C#, qui n'ont pas intégré bigints.
    pour une précision arbitraire, il est O((nombre de chiffres)^2), voir le commentaire de @Peters réponse.
    Je ne vois pas pourquoi c'est vrai. Après tout, cela dépend de la représentation interne de bigints. Si bigints constituée de plusieurs morceaux (correspondant à la représentation N = n_0 + 10^kn_1 + 10^2kn_2 etc.), la multiplication par 10 peut être très efficace. Avez-vous mesurer la performance de l'analyse en Python?
    quand vous parlez de cette conversion, vous avez généralement supposer que la base de la chaîne (10) est différente de la base utilisée par la représentation interne. Sinon, il est possible de faire en O(1). Ad nous parlons de la complexité, pas la performance.

    OriginalL'auteur Vlad