Complexité de calcul des symboles de comptage

Question

considérer la fonction de comptage $ \ {x \} ^ * \ rightarrow \ mathbb n $ comporte le nombre d'occurrences du symbole $ x $ .

Je suis confus à propos de la complexité (asymptotique) de calcul de cette fonction, où la sortie doit être représentée dans un système non unitaire (par exemple, binaire) . Mon intuition suggère fortement que cela devrait être linéaire, c'est-à-dire $ o (n) $ où $ n $ est le nombre d'occurrences du symbole $ x $ dans l'entrée.

Autant que ma compréhension, il y a plusieurs interprétations de calcul - par exemple,

• Machines de Turing mono-bande, pour lesquelles ma meilleure idée a le temps d'exécution $ \ oméga (n ^ 2 \ log n) $ Je pense (la classe $ \ journal n $ provient de l'hypothèse que la fonction binaire successeur a $ \ omega (n) $ heure d'exécution, où $ n $ est la longueur d'une représentation binaire d'un nombre naturel et de la $ n ^ 2 $ provient de l'hypothèse que la machine Turing doit parcourir tout le $ x $ 'S pour atteindre son compte actuel),
• Machines de Turing multi-bandes, pour lesquelles je pense avoir une idée de l'heure d'exécution $ \ oméga (n \ journal n) $
, ,
• Machines d'accès aléatoire, que je ne sais pas du tout.

Donc, ma question est la suivante.

Quelle est la complexité de calcul de la fonction de comptage dans les différents modèles de calcul? Est-ce linéaire dans l'un d'entre eux?

Si du tout est pertinent, je demande au point de vue de l'algèbre abstraite, où j'essaie d'évaluer la complexité de calcul du problème de mot dans un groupe spécifique.

Answer 1

Turing Machines est un joli modèle avec plusieurs avantages, principalement leur simplicité, mais ils ne sont pas le premier choix lors de l'analyse d'algorithmes. Les algorithmes sont généralement implicitement analysés sur le modèle de la machine RAM, et dans certains cas, sur le Modèle BSS .

Voici quelques commentaires sur la complexité informatique du comptage dans divers modèles:

Machine de Turning mono-bande: Celles-ci ne sont envisagées que car elles sont relativement faciles à prouver des limites inférieures. Ils sont encore moins réalistes un modèle de calcul que des machines à turing multi-bande.

Multi-bande Turing Machine: Il s'agit d'un exemple standard de complexité amortie qu'un compteur croissant peut être mis en œuvre à l'aide de $ O (1) $ Opérations de bits amorties. C'est parce que la moitié du temps, un seul bit change, un quart de temps, seulement deux bits, etc., pour un nombre total de bits modifiés, ce qui est 1/2 + 2 $ / 4 + 3/8 + \ CDOTS= 2 $ . La complexité de la machine Turing est linéaire en cela, et la comptage peut donc être mise en œuvre dans $ o (n) $ .

.

machine RAM: une machine RAM consiste en fini de nombreux registres et une mémoire au hasard. Les registres sont $ O (\ journal n) $ -bits longs, où $ n $ est la taille de l'entrée. Les opérations raisonnables sur les registres prennent une durée constante. En particulier, augmenter un compteur qui peut compter jusqu'à $ \ mathit {poly} (n) $ prend $ O (1 ) $ le pire cas temps. En particulier, votre fonction fonctionnera dans $ O (n) $ .

machine BSS: Il faut faire attention lorsque vous effectuez des arithmétiques sur de grands nombres. Sur la machine RAM, l'arithmétique prend du temps constant uniquement si la magnitude des opérandes est $ \ mathit {poly} (n) $ . Une machine BSS permet d'accéder à des registres spéciaux qui stockent des valeurs dans certains champs, disent les chiffres réels. Vous pouvez effectuer des arithmétiques et des comparaisons à temps constant, mais pas de fonctions comme le sol. Vous n'êtes également pas autorisé à utiliser de telles valeurs pour l'indexation. (Si vous ne vous limitez pas assez, vous vous en résoudre bientôt assis dans une période polynomiale.) Vous pouvez penser à une machine BSS comme étant accommodant des opérations à virgule flottante, qui prennent en pratique une durée constante, tout en ignorant la précision finie impliquée dans elles. .