Complexité en espace : log n bafoué ?

Bonjour,

Je me pose la question (existentielle) suivante :
Si je veux utiliser un tableau enregistrant des entiers de 1 à n dans un ordre quelconque, je vais dire que j'ai besoin d'un espace en O(n) et, a priori, ça ne va pas choquer.
Pourtant, pour stocker ces n entiers j'ai besoin de n log(n) bits. Ce qui nous fait alors du O(n log n).
D'où vient alors la disparition du log n ? Du fait que si n n'est pas trop grand ( < 2^32), on peut le stocker sur un mot mémoire et on a alors besoin de n mots mémoire ? Mais dans ce cas, on se base sur un certain nombre d'hypothèses (n < 2^32, machine 32 bits) qu'une complexité théorique ne devrait pas prendre en compte...
Quelqu'un a une explication ?

Merci d'avance ;)

Je crois que vous avez vous même donné la réponse à votre question.
Les exposés théoriques font toujours des hypothèses simplificatrices, le plus souvent implicites faisant disparaître une partie de la complexité. De plus je ne sais pas s'il est possible de faire autrement.

il faut dire que quand on parle de complexité, ca n'est jamais dans l'abstrait, c'est toujours une complexité en quelque chose. quand on parle d'un algorithme et de place en memoire, on va implicitement donner une complexité en "nombre de cases", en gros... et ce pour etre le plus general possible, cad independant de la maniere dont les ordinateurs stockent les données.

quand on veut l'implementer, on se rend compte qu'une "case" prend log(n) bits environ. donc une complexité de O(n) "cases" est exactement la meme chose qu'une complexité en O(n log n ) bits. donc je ne crois pas qu'on ai fait disparaitre une partie de la complexité. et c'est justement parce qu'on ne tient pas compte des specifité des ordinateurs qu'on parle de complexité en O(n).

Citation:

---

Envoyé par jobherzt

c'est justement parce qu'on ne tient pas compte des specifité des ordinateurs qu'on parle de complexité en O(n).

---

C'est vrai qu'on dit "j'ai besoin de n cases donc ma complexité est en O(n)" sans vraiment faire attention à ce que sont nos cases. Cependant si nos ordinateurs ne pouvaient écrire ou lire qu'un bit à la fois, nos complexités en espace (et en temps aussi) seraient différentes (avec un facteur log n en bonus).

Si je considère un champ de bits dans lequel je stocke n*log n bits. Est-ce que je vais dire que la complexité en espace de ce champ de bits est de O(n log n) car j'ai n log n cases ou bien O(n) car je peux regrouper mes bits par lots de log n pour les mettre ensemble dans une case plus grosse ?

disons qu'il n'y a pas de regle absolue. dans ce cas la, tu parle explicitement de bits, donc ton unité de base, celle qui est parlante et qui a du sens, c'est le bit. donc dans ce cas je parlerais de O(n*log n), c'est ce qui me semble le plus cohérent. parce qu'a la limite, tu pourrais considérer que tu as une complexité en O(1) champs de bits de n cases :) d'un certain point de vue c'est juste, mais pas tres utile.

l'exemple le plus flagrant, c'est pour la factorisation des entiers: si tu veux factoriser un entier N, n'importe quel algo est polynomial en O(N).. pourtant, on ne considere pas que ce probleme est polynomial !! l'unité qui a un sens, c'est le nombre de chiffre de N, et la c'est bien exponentiel..

Quand on parle de complexité, c'est par rapport à la taille de l'instance.

Par exemple, pour un entier n, la complexité spatiale est : log_2 n. On pourrait imaginer une représentation de n tel que sa complexité spatiale soit n, mais ça n'aurait pas trop d'interêt.

Un algorithme qui par exemple cherche à déterminer si m<n pourrait se faire en : O(min(log_2 m, log_2 n)). On a ce qu'on appelle un algorithme linéaire en la taille de l'instance (c'est linéaire et non pas logarithmique). L'opération élémentaire utilisée est < valable pour les entiers entre 0 et 9 et se fait en O(1).


Pour un tri, on considère que la complexité spatiale d'un tableau de taille n est en O(n), ce qui implique clairement que les entiers sont de taille limités. Ce qui est en général le cas. Si tu dis que l'on prend en compte la taille des entiers, il faut trouver un majorant t de la taille de tous les entiers du tableau. La complexité serait alors en : O(n ln n * t) étant donné que la fonction < ne se fait plus en O(1) mais en O(t).


En fait, si l'on suppose toujours que l'opération < se fait en temps constant, la complexité sera toujours en O(n ln n).

On effectue souvent cette simplification sur les opérations simples, comme +, * ou encore < car en général, on travaille sur des entiers bornés et les calculs sur nos processeurs se font en temps constant.
Par contre, si tu fais des travaux sur de grands entiers (comme en cryptologie), il faut prendre en compte tout ça (par exemple : + est en ln(n), < est en ln(n). Pour *, il existe des méthodes basées sur les transformées de Fourier pour aller plus vite...