Complexité temporelle de l'addition

Wikipedia répertorie la complexité temporelle de l'addition comme $n$ , où $n$ est le nombre de bits.

S'agit-il d'une borne inférieure théorique rigide? Ou est-ce simplement la complexité de l'algorithme connu le plus rapide actuellement. Je veux savoir, car la complexité de l'addition souligne toutes les autres opérations arithmétiques et tous les algorithmes qui les utilisent.

Est-il théoriquement impossible d'obtenir un algorithme d'addition qui s'exécute en $o(n)$ ? Ou sommes-nous liés à une complexité linéaire pour l'addition.

algorithms algorithm-analysis arithmetic Tobi Alafin
la source

Réponses:

Si votre algorithme utilise asymptotiquement moins de fois, il n'a pas assez de temps pour lire tous les chiffres des nombres qu'il ajoute. Vous devez imaginer que vous manipulez de très grands nombres (stockés par exemple dans des fichiers texte de 8 Mo). Bien sûr, l'addition peut se faire très rapidement par rapport à la valeur des nombres; il s'exécute en temps , si est la valeur de la somme. $n$ $\mathcal{O}(\log(N))$ $N$

Cela ne signifie pas que vous pouvez accélérer un peu les choses; si votre processeur gère 32 bits à chaque opération, alors vous utilisez fois, mais c'est toujourset non. $\frac{n}{32}$ $\mathcal{O}(n)$ $o(n)$

Lieuwe Vinkhuijzen
la source

Lire toutes les données théoriquement nécessaires. Pour l'addition de deux nombres

. Le calcul de

peut être effectué en fonctionnement

, par décalage. Ajout d'un

. Considérez cela. Si vous ne trouvez pas une estimation plus rapide de la somme, affinez cette estimation jusqu'à ce qu'elle soit correcte. En moins de

opérations?

a

$a$

b, a : a \geq b, a + b \leq 2 a

$b, a: a \ge b, a + b \le 2a$

2 a

$2a$

O (1)

$O(1)$

0

$0$

n

$n$

Tobi Alafin

Oui, c'est une nécessité théorique, car: chaque bit de l'entrée est utilisé de manière non triviale dans la sortie , où par non trivial, je veux dire que ce n'est pas la fonction d'identité. Dans votre exemple

, si

peut être calculé en temps

dépend du modèle de calcul: si l'ajout d'un

est une opération à temps constant, alors oui. Si vous avez accès à la RAM, vous avez besoin de

pour écrire l'adresse du bit si vous connaissez déjà la longueur de

, ou

2 a

$2a$

2 a

$2a$

O (1)

$O(1)$

0

$0$

O (\log (n))

$O(\log(n))$

a

$a$

O (n)

$O(n)$ temps si vous devez lire tout

pour le savoir. Dans ce

exemple, le nombre de bits de sortie sont des fonctions triviales de bits d'entrée.

a

$a$

2 a

$2a$

Lieuwe Vinkhuijzen

J'ai un algorithme qui trouve la longueur d'

dans

. Il utilise la recherche binaire.

a

$a$

O (\log n)

$O(\log n)$

Tobi Alafin

@TobiAlafin Si votre modèle prend en charge l'adressage RAM, votre recherche binaire s'exécute par étapes

, corrigez. Sur Turing Machine, et dans un fichier texte non chargé dans la mémoire principale, cela prend du temps

. Dans les deux cas, pour répondre à votre question, avec ou sans adressage RAM pour accélérer la recherche, votre algorithme devra regarder tous les bits de l'entrée pour calculer

. Supposons qu'il ne l'ait pas fait, et sur une entrée de

bits, il n'inspecte pas le

bit. Ensuite, je pourrais retourner ce bit, et cela donnerait la mauvaise réponse.

O (\log n)

$O(\log n)$

O (n)

$O(n)$

a + b

$a+b$

42

$42$

6

$6$

Lieuwe Vinkhuijzen

Ω (n)

$\Omega(n)$

Pour que l'analyse de complexité ait un sens formel, vous devez spécifier un modèle de calcul formel dans lequel l'algorithme dans l'objet est exécuté, ou, à tout le moins, un modèle de coût , qui spécifie quelles sont les opérations de base et leurs coûts.

$\Theta(1)$

$\Theta(|x|)$

Maintenant, les opérations peuvent-elles avoir un coût inférieur à cela? Cependant, vous devrez peut-être définir formellement un modèle de calcul dans lequel cela peut se produire.

tri rapide
la source

Θ (\log n)

$\Theta(\log n)$

n

$n$

$\Omega(n)$

Imaginez que votre algorithme ajoute avec succès 1010100110 et 0010010110 sans lire chaque bit. Pour que votre algorithme puisse ajouter des entrées arbitraires , je devrais être capable de retourner aléatoirement n'importe lequel de ces bits, et l'algorithme génère toujours une addition correcte (mais différente). Mais si votre algorithme ne lit pas tous les bits, comment pourrait-il dire que l'entrée inversée était différente de l'entrée d'origine?

murrdpirate
la source

n

$n$

Absolument. Il vous suffit de définir ce que signifie "approximatif" dans votre algorithme. Selon cette définition, l'ajout des deux bits les plus significatifs pourrait être une somme approximative, ce qui pourrait être fait en temps o (n) . Lorsque vous mentionnez l'algorithme "addition", je pense que nous considérons tous que cela signifie que la réponse doit être exacte.

murrdpirate