Comments on: Complexité algorithmique : pourquoi tant de “n” ? http://sametmax.com/complexite-algorithmique-pourquoi-tant-de-n/ Du code, du cul Sat, 07 Nov 2015 11:08:18 +0000 hourly 1 http://wordpress.org/?v=4.1 By: kontre http://sametmax.com/complexite-algorithmique-pourquoi-tant-de-n/#comment-24876 Sun, 27 Apr 2014 20:00:42 +0000 http://sametmax.com/?p=10051#comment-24876 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 http://sametmax.com/complexite-algorithmique-pourquoi-tant-de-n/#comment-24777 Sat, 26 Apr 2014 12:17:46 +0000 http://sametmax.com/?p=10051#comment-24777 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 http://sametmax.com/complexite-algorithmique-pourquoi-tant-de-n/#comment-24741 Fri, 25 Apr 2014 19:26:13 +0000 http://sametmax.com/?p=10051#comment-24741 https://www.coursera.org/course/algoprog

(j’ai chié mon lien désolé …)

]]>
By: Tim http://sametmax.com/complexite-algorithmique-pourquoi-tant-de-n/#comment-24740 Fri, 25 Apr 2014 19:22:37 +0000 http://sametmax.com/?p=10051#comment-24740 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 http://sametmax.com/complexite-algorithmique-pourquoi-tant-de-n/#comment-24716 Fri, 25 Apr 2014 10:18:52 +0000 http://sametmax.com/?p=10051#comment-24716 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 http://sametmax.com/complexite-algorithmique-pourquoi-tant-de-n/#comment-24711 Fri, 25 Apr 2014 08:36:43 +0000 http://sametmax.com/?p=10051#comment-24711 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 http://sametmax.com/complexite-algorithmique-pourquoi-tant-de-n/#comment-24654 Thu, 24 Apr 2014 18:21:38 +0000 http://sametmax.com/?p=10051#comment-24654 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 http://sametmax.com/complexite-algorithmique-pourquoi-tant-de-n/#comment-24621 Thu, 24 Apr 2014 07:43:23 +0000 http://sametmax.com/?p=10051#comment-24621 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 http://sametmax.com/complexite-algorithmique-pourquoi-tant-de-n/#comment-24620 Thu, 24 Apr 2014 07:40:56 +0000 http://sametmax.com/?p=10051#comment-24620 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 http://sametmax.com/complexite-algorithmique-pourquoi-tant-de-n/#comment-24569 Wed, 23 Apr 2014 10:23:55 +0000 http://sametmax.com/?p=10051#comment-24569 Ouai, je vais déplacer les parenthèses à la fin, ça sera plus clair.

]]>