Un programme sur lequel je travaille convertit un tableau d'entiers en une chaîne à l'aide du générateur de chaîne. J'essaie de déterminer la complexité temporelle de cette approche.Quelle est la complexité temporelle de StringBuilder.append() dans java?
Départ: https://stackoverflow.com/a/7156703/7294647
Fondamentalement, il est clair pas ce que la complexité du temps est pour StringBuilder#append car elle dépend de sa mise en œuvre, de sorte que vous ne devriez pas avoir à vous soucier de.
Il pourrait y avoir une manière plus efficace d'approcher votre conversion int [] - String en fonction de ce que vous essayez réellement d'accomplir.
Si le StringBuilder a besoin d'augmenter sa capacité, cela implique la copie de l'ensemble du tableau de caractères dans un nouveau tableau. Vous pouvez éviter cela en réglant d'abord la capacité pour ne pas avoir à le faire. (Cela devrait être facile puisque vous connaissez la longueur du tableau int et le nombre maximum de caractères dans la représentation String d'un int.)
Si vous évitez la nécessité d'accroître la capacité, la complexité semble être juste Sur). Lorsque vous ajoutez, vous copiez simplement le tableau de caractères du String à la fin du tableau de caractères dans le StringBuilder.
(Oui, cela dépend de la mise en œuvre, mais ce serait une assez mauvaise mise en œuvre de StringBuilder si elle ne pouvait pas ajouter à O (n).)
Il est très probablement encore plus rapide que cela; il pourrait utiliser quelque chose comme un 'LinkedList' pour O (1) l'ajout. –
Je ne suis pas sûr de ça. Si c'est O (1) cela veut dire que vous copiez la liste chaînée elle-même au lieu des valeurs - et ne vous poseriez-vous pas des problèmes si vous vouliez ajouter quelque chose à la fin? Cela changerait l'original. –
Que voulez-vous dire par « l'efficacité »? Quel est le critère que vous essayez d'optimiser? –
Il convient également de souligner que vous devez définir l'efficacité d'une approche par rapport à une autre approche réalisable. Comme dans, il faut de grandes quantités de carburant pour lancer un satellite en orbite, [ce n'est pas très efficace] (https://space.stackexchange.com/a/17925) (comme en puissance utilement dépensé); mais en l'absence d'alternative, l'approche "inefficace" est tout ce que vous pouvez faire, donc l'inefficacité est largement hors de propos. Alors, quelle est votre alternative au constructeur de cordes? –