Quel est le temps prévu de la complexité de la vérification de l'égalité de deux des chaînes arbitraires?

Question

Le simple (naïf?) la réponse devrait être: O(n) où n est la longueur de la plus courte chaîne.Parce que, dans le pire des cas, vous devez comparer chaque paire de caractères.

So far So good.Je pense que nous pouvons tous convenir que la vérification de l'égalité de deux longueur égale les chaînes nécessite O(n) le temps d'exécution.

Cependant beaucoup (la plupart?) langues (je suis à l'aide de Python 3.7) stocker les longueurs de chaînes pour permettre la constante de temps des recherches.Ainsi, dans le cas de deux longueur inégale les chaînes, vous pouvez simplement vérifier len(string_1) != len(string_2) en temps constant.Vous pouvez vérifier que Python 3 n'a en effet de faire de cette optimisation.

Maintenant, si nous vérifions l'égalité de deux vraiment des chaînes arbitraires (de longueur arbitraire), alors il est plus probable (infiniment, je crois) que les chaînes de longueur inégale que de longueur égale.Qui (statistiquement) garantit que nous pouvons presque toujours les comparer en temps constant.

Nous pouvons donc comparer les deux des chaînes arbitraires en O(1) en moyenne, avec un très rare pire des cas en O(n).Devrions-nous considérer les chaînes de comparaisons puis à O(1) de la même manière, nous considérons la table de hachage de recherches à O(1)?

Answer 1

Afin de discuter de l'heure prévue de la complexité d'une opération, vous devez spécifier une distribution sur les entrées, et aussi d'expliquer ce que vous entendez par $n$.

On doit être prudent, cependant.Considérons, par exemple, la suggestion dans les commentaires, à envisager une sorte de distribution sur les mots de longueur au plus 20.Dans ce cas, la comparaison des chaînes est clairement $O(1)$, depuis 20 est juste une constante.Il y a plusieurs façons de l'éviter:

• Demander un non-asymptotique du temps de la complexité.Depuis le temps de la complexité est fortement dépendante du modèle de calcul, vous pouvez compter (par exemple) le nombre de cellules de mémoire accessible.

• Vous pouvez spécifier une distribution des intrants qui dépend d'un paramètre $m$, et puis demander la complexité asymptotique en termes de $m$.

Ici est un exemple.Étant donné deux aléatoire chaînes binaires de longueur $n$, il y aura environ 4 raccordements en attente.En revanche, si les chaînes sont choisis au hasard à partir de la collection $0^i1^{n-i}$, le nombre d'accès seront à peu près $(2/3)n$.Ces deux distributions peuvent être séparés, même si nous utilisons la notation asymptotique:l'algorithme s'exécute en $O(1)$ sur la première distribution, et dans $ heta(n)$ sur la deuxième.

Un autre problème est le sens de l' $n$.Considérons par exemple une chaîne de caractères $0^m$, où m $\sim G(1/2)$ est géométrique variable aléatoire.Lorsqu'il est exécuté sur les apports de longueurs $a,b$, le temps d'exécution est $ heta(\min(a,b))$.Comment devrions-nous nous exprimer cela en termes de $n = a+b$?Un choix est à demander pour le temps d'exécution étant donné que l'entrée de la longueur est $n$.Dans ce cas, $$ \mathbb{E}[\min(a,b)] = \sum_{a=1}^{n-1} \frac{(1/2)^a (1/2)^{n-1}}{\sum_{a'=1}^{n-1} (1/2)^{a'} (1/2)^{n-1-a'}} \min(a,n-un) = \frac{1}{n-1} \sum_{a=1}^{n-1} \min(a,n-a) \approx \frac{n}{4}, $$ de sorte que le temps d'exécution est prévu $ heta(n)$.