Comments on: Complexité algorithmique : pourquoi tant de “n” ?

By: kontre

kontre — Sun, 27 Apr 2014 20:00:42 +0000

Attention avec vos exemples: à partir du moment où votre nombre d'élément est fixé, on ne peut plus parler de complexité algorithmique, puisque plus rien ne peut varier: on sera alors toujours en temps constant: si n=100, O(n) == O(100) == O(1). L'exemple de Xavier serait par exemple:

    l=list(range(0,n))
    l.insert(99,0) # O(n)
    x=l.pop(0) # O(n)
    #mais
    l.append(98) # O(1)
    x=l.pop() # O(1)

Pour Oyabi, on aurait plutôt ça en O(n*m*p):

for i in range(n):
    for j in range(m):
        for k in range(p):
            afficher "Coucou cuicui, c'est moi super connard."

et ça en O(n**3):

for i in range(n):
    for j in range(2*n):
        for k in range(3*n+8):
            afficher "Coucou cuicui, c'est moi super connard."

By: Xavier Combelle

Xavier Combelle — Sat, 26 Apr 2014 12:17:46 +0000

Ajouter ou retirer un élément a une position quelconque d’une liste est en O(n). C’est seulement si l’élément est vers la fin que ces accès sont en O(1).

donc
l=list(range(0,1000)) l.insert(99,0) # O(n) x=l.pop(0) # O(n) #mais l.append(98) # O(1) x=l.pop() # O(1)

By: Tim

Tim — Fri, 25 Apr 2014 19:26:13 +0000

https://www.coursera.org/course/algoprog (j'ai chié mon lien désolé ...)

By: Tim

Tim — Fri, 25 Apr 2014 19:22:37 +0000

Il y a un très bon MOOC sur les algo et qui reprend les notions de complexité. Il y a des TPs vraiment prise de chou ... mais c'est super enrichissant. Pas en python mais en java, mais rien n'empêche après de les refaire en python ;)

By: Sam

Sam — Fri, 25 Apr 2014 10:18:52 +0000

Disons plutôt si jusqu’à x était un facteur de jusqu’à z qui était un facteur de jusqu’à y, tu aurais O(n^3).

By: Oyabi

Oyabi — Fri, 25 Apr 2014 08:36:43 +0000

Donc dans l’exemple que j’ai mis plus haut, avec i,j,k=0, nous aurions O(m*n*p), c’est bien ça ?
En revanche si nous avions “jusqu’à 10” pour chaque boucle, nous aurions O(n^3).

By: kontre

kontre — Thu, 24 Apr 2014 18:21:38 +0000

Plutôt qu’un ordre de grandeur, je dirais plutôt si elles sont liées. Plus précisément, O(m*n*p) == O(n^3) si m, n et p sont proportionnels.

By: Sam

Sam — Thu, 24 Apr 2014 07:43:23 +0000

O(n * m * p) si les variables sont d’ordre de grandeur différentes, O(n^3) si elles sont de même ordre de grandeur.

By: Oyabi

Oyabi — Thu, 24 Apr 2014 07:40:56 +0000

Intéréssant tout ca.
Par contre si tu as quelque chose dans ce genre :
pour i jusqu'a 10 pour j jusqu'a 15 pour k jusqu'a 2 afficher "Coucou cuicui, c'est moi super connard." finpour finpour finpour
Tu as un O(n^3) ou bien O(n*m*p) ?

By: Sam

Sam — Wed, 23 Apr 2014 10:23:55 +0000

Ouai, je vais déplacer les parenthèses à la fin, ça sera plus clair.