Comment pouvons-nous supposer que les opérations de base sur les nombres prennent un temps constant?

74

Normalement, dans les algorithmes, nous ne nous soucions pas de la comparaison, de l'addition ou de la soustraction de nombres - nous supposons qu'ils sont exécutés dans le temps . Par exemple, nous supposons cela lorsque nous disons que le tri basé sur la comparaison est , mais lorsque les nombres sont trop gros pour être insérés dans des registres, nous les représentons normalement sous forme de tableaux, de sorte que les opérations de base nécessitent des calculs supplémentaires par élément. $O(1)$ $O(n\log n)$

Existe-t-il une preuve montrant que la comparaison de deux nombres (ou d'autres fonctions arithmétiques primitives) peut être effectuée dans ? Si non, pourquoi dit-on que le tri basé sur la comparaison est ? $O(1)$ $O(n\log n)$

J'ai rencontré ce problème quand je répondu à une question SO et je compris que mon algorithme n'est pas parce que , tôt ou tard , je dois traiter avec grand-int, aussi il n'a pas été algorithme pseudo polynôme, il était . $O(n)$ $P$

algorithms complexity-theory algorithm-analysis time-complexity reference-question Raphaël
la source

3

N

$N$

w

$w$

n = N w

$n=Nw$

O (N w \log N) = O (n \log n)

$O(Nw \log N) = O(n \log n)$

2

O (1)

$O(1)$

75

Pour les personnes comme moi qui étudient les algorithmes pour gagner leur vie, le modèle de calcul standard du XXIe siècle est la RAM entière . Le modèle est conçu pour refléter le comportement des ordinateurs réels avec plus de précision que le modèle de la machine de Turing. Les ordinateurs du monde réel traitent des nombres entiers de plusieurs bits en temps constant en utilisant un matériel parallèle; pas des nombres entiers arbitraires , mais (car la taille des mots augmente régulièrement dans le temps), les nombres entiers non plus de taille fixe .

$w$ $w$ $n$ $O(1)$

$w$ $w \ge \log_2 n$ $n$ $w$ $O(n\log n)$ $O(n^2)$ $O(nw)$

$w = \Theta(\log n)$ $w = \Omega(\log^{2+\varepsilon} n)$

$w$

Mise à jour: je devrais également mentionner qu'il existe des exceptions au "modèle standard", comme l'algorithme de multiplication entier de Fürer , qui utilise des machines de Turing à bandes multiples (ou, de manière équivalente, la "bit RAM"), ainsi que la plupart des algorithmes géométriques, qui sont analysés de manière théorique. modèle "réel RAM" propre mais idéalisé .

Oui, c'est une boîte de Pandore.

JeffE
la source

3

Je sais que je suis juste censé voter, mais je ne peux pas m'empêcher de le dire: c'est la meilleure réponse. L'astuce est que (1) les opérations arithmétiques sont constante de temps , par définition , et c'est OK parce que , en théorie , vous pouvez choisir un modèle, et (2) vous devriez avoir quelques raisons de choisir un certain modèle, et cette réponse explique ce qu'ils sont.

Départ

n

$n$

m

$m$

P

$P$

1

w

$w$

w

$w$

N

$N$

0

$0$

M

$M$

N \log_{w} M = (N \lg M) / (\lg w)

$N\log_w M = (N\lg M)/(\lg w)$

O (N M)

$O(NM)$

M

$M$

JeffE

Existe-t-il des algorithmes analysés dans le modèle Real RAM qui ne sont pas secrètement des algorithmes "Order Type RAM"? Je n'y ai jamais beaucoup réfléchi, mais je ne peux pas trouver rapidement un exemple qui ne le soit pas.

Louis

1

O (n^{3})

$O(n^3)$

O (n^{4})

$O(n^4)$

24

$n$ $O(1)$ $O(n)$

Massimo Cafaro
la source

De votre article cité en référence: "peut être mesuré de deux manières différentes: une en termes de nombres entiers testés ou multipliés, et une en termes de nombre de chiffres binaires (bits) dans ces nombres entiers", mais ce n'est pas vrai. devrait toujours mesurer par la taille de l'entrée.

1

n

$n$

θ (n^{1 / 2})

$\theta(n^{1/2})$

P

$P$

n

$n$

En passant, les algorithmes pseudo-polynomiaux peuvent en réalité être utiles si l'ordre de grandeur de leurs paramètres dans des instances réelles est raisonnablement faible. L'exemple le plus célèbre est probablement l'algorithme pseudo-polynomial permettant de résoudre le problème du sac à dos.

Massimo Cafaro

P

$P$

P

$P$

O (n \log n)

$O(n \log n)$

n

$n$

O (1)

$O(1)$

n

$n$

O (n) = O (2^{l g n})

$O(n) = O(2^{lg n})$

l g n

$lg n$ est la taille d'entrée, l'algorithme est exponentiel dans la taille d'entrée! Penses-y. Vous pouvez maintenant comprendre ce que je veux dire par "Cela dépend du contexte".

Massimo Cafaro

16

Pour répondre à la question comme indiqué: les algorithmes le font simplement, assez souvent, en utilisant le modèle RAM. Pour le tri, dans de nombreux cas, les gens analysent même le modèle de comparaison plus simple , que je discute un peu plus dans la réponse liée.

Pour répondre à la question implicite de savoir pourquoi ils le font: je dirais que ce modèle a un assez bon pouvoir prédictif pour certains types d’algorithmes combinatoires, dans lesquels les nombres sont tous "petits" et, sur de vraies machines, s'intègrent dans des registres.

Pour répondre implicitement au sujet des algorithmes numériques: Non, le vieux modèle de mémoire vive n'est pas la norme. Même l'élimination gaussienne peut nécessiter quelques précautions. Typiquement, pour les calculs de rangs, le Schmaz Lemma entrera (par exemple, Section 5 ici ). Un autre exemple canonique est l’analyse de l’algorithme ellipsoïde, qui nécessite quelques précautions d’analyse.

Et enfin: les gens ont déjà pensé au tri des chaînes , même récemment.

Mise à jour: Le problème avec cette question est que "nous" et "supposons" ne sont pas spécifiés avec autant de précision. Je dirais que les personnes qui travaillent dans le modèle de RAM ne font pas des algorithmes numériques ou de la théorie de la complexité (où déterminer la complexité de la division était un résultat célèbre ).

Louis
la source

Hmmmm, semble que c'est une réponse intéressante ....

Y a-t-il une raison pour laquelle il ne répond pas complètement à la question?

Louis

7

$O(1)$ $O(1)$

python -mtimeit "$a * $b"$a $10^{\{1,2,...,66\}}$ $b = 2*$a

$10^{50}$ $\log_{10}(\tt{sys.maxint})$

Dougal
la source

O (n)

$O(n)$

O (n \cdot \log n \cdot \log m)

$O(n \cdot \log n \cdot \log m)$

7

$O(1)$

$O(\log M)$ $O (N \log N)$ $O (N \log N \log M)$

$M$

Erel Segal-Halevi
la source

O (\log m)

$O(\log m)$

O (\log n)

$O(\log n)$

m

$m$

O (l o g N)

$O(log N)$

n

$n$

n^{n^{n}}

$n^{n^n}$

Vous avez raison, j'ai corrigé ma réponse.

Erel Segal-Halevi,

4

Je dirais que nous supposons généralement des opérations arithmétiques O (1) parce que nous agissons généralement dans le contexte d'entiers 32 bits ou d'entiers 64 bits ou de nombres à virgule flottante IEEE 754. O (1) est probablement une assez bonne approximation pour ce genre d'arithmétique.

Mais en général, ce n'est pas vrai. En général, vous avez besoin d'un algorithme pour effectuer des additions, des soustractions, des multiplications et des divisions. La calculabilité et la logique de Boolos, Burgess et Jefferies nous viennent à l’esprit pour en comprendre les preuves, en ce qui concerne quelques systèmes formels différents, les fonctions récursives et les machines Abacus, du moins dans ma 4e édition.

Vous pouvez consulter les termes du lambda-calcul pour la soustraction et la division avec les chiffres de l'Église pour une explication facile à comprendre sur la raison pour laquelle ces deux opérations ne sont pas O (1). Il est un peu plus difficile de voir pour l'addition, la multiplication et l'exponentiation, mais c'est là si vous considérez la forme des chiffres d'église eux-mêmes.

Bruce Ediger
la source

Comment pouvons-nous supposer que les opérations de base sur les nombres prennent un temps constant?

Réponses: