Salut les kheys.

J'aimerais savoir pourquoi l'opération avec le zip a une complexité en n^2 ? Et pourquoi un simple print a une complexité en O(n) alors que ça devrait être en O(1) ? J'ai du mal à faire la différence entre complexité moyenne et maximale.

Merci d'avance.

Mec il est 1:00 va te coucher

Le 08 janvier 2018 à 01:13:13 Submerger a écrit :
Mec il est 1:00 va te coucher

Je dois vraiment comprendre ce truc.

Ayez pitié les kheys, j'me lève dans 5 heures. J'aimerais dormir.

Pour le print, il doit afficher chacune des lettre

Pour le zip c'est parceque pour chaque liste il doit aussi faire une opération O(n) donc ça fait O(n) * O(n) il me semble

Le 08 janvier 2018 à 01:17:04 Shirk a écrit :

Le 08 janvier 2018 à 01:13:13 Submerger a écrit :
Mec il est 1:00 va te coucher

Je dois vraiment comprendre ce truc.

Ayez pitié les kheys, j'me lève dans 5 heures. J'aimerais dormir.

Je up pour t'aider khey !

Le 08 janvier 2018 à 01:18:15 Kamihate a écrit :

Le 08 janvier 2018 à 01:17:04 Shirk a écrit :

Le 08 janvier 2018 à 01:13:13 Submerger a écrit :
Mec il est 1:00 va te coucher

Je dois vraiment comprendre ce truc.

Ayez pitié les kheys, j'me lève dans 5 heures. J'aimerais dormir.

Je up pour t'aider khey !

Cimer khey !

Le 08 janvier 2018 à 01:18:15 MegacityFutur a écrit :
Pour le print, il doit afficher chacune des lettre

Pour le zip c'est parceque pour chaque liste il doit aussi faire une opération O(n) donc ça fait O(n) * O(n) il me semble

Merci khey, mais pourquoi alors a-t-on une complexité moyenne différente de la maximale, si dans les deux cas il doit faire une opération O(n) pour chaque liste ?

Le zip est en O(n), mais c'est le dict() qui prend O(n^2) en pire cas (chaque ajout d'une entrée fait du O(n) pire cas, tu ajoutes n entrées)
le print(dico) est en O(n) parce qu'il y a n entrées à afficher

Le 08 janvier 2018 à 01:20:44 JeanCroutenard a écrit :
Le zip est en O(n), mais c'est le dict() qui prend O(n^2) en pire cas (chaque ajout d'une entrée fait du O(n) pire cas, tu ajoutes n entrées)
le print(dico) est en O(n) parce qu'il y a n entrées à afficher

Aaaaaaaaaaaaaah d'accord j'ai capté ! Merci !

Je vais enfin pouvoir plonger dans mon lit. Merci les kheys !

Je pense que c'est en n^2 si tous les mots (ou tableaux) composants x ont une taille différentes.

Dans ce cas là, quand il ajoute dans le dict il va devoir checker si la taille (la clé) n'est pas déjà dans le dict; vu que ca ne sera jamais le cas, il chercheras parmi toutes les j entrées à ce moment là et rajouteras la nouvelle clé à la fin du dict. Tu as n mots donc ca fera en gros n^2: http://www.wolframalpha.com/input/?i=sum(i,i%3D0,i%3Dn)

J'étudie aussi python et tu m'as rappelé que je ne comprends rien

Le 08 janvier 2018 à 01:30:10 Hola-Chica-3 a écrit :
Je pense que c'est en n^2 si tous les mots (ou tableaux) composants x ont une taille différentes.

Dans ce cas là, quand il ajoute dans le dict il va devoir checker si la taille (la clé) n'est pas déjà dans le dict; vu que ca ne sera jamais le cas, il chercheras parmi toutes les j entrées à ce moment là et rajouteras la nouvelle clé à la fin du dict. Tu as n mots donc ca fera en gros n^2: http://www.wolframalpha.com/input/?i=sum(i,i%3D0,i%3Dn)

C'est pas exactement comme cela que fonctionne les dictionnaires en Python (généralement appelés HashMap dans les autres langages).
Quand on ajoute une entrée à un dictionnaire, on ne check pas toutes les clés existantes, ça serait beaucoup trop long.
On va juste calculer un "empreinte" (hash) de l'objet, cette empreinte est en fait un nombre, et tu vas regarder ce qui se situe dans ton dictionnaire à l'index de ce nombre. En interne, ton dictionnaire fonctionne en fait comme un tableau avec beaucoup de cases vides qui sont remplies quand tu ajoutes une entrée.
Le pire des cas survient lorsque tu veux ajouter plusieurs objets qui ont la même empreinte. Tu vas regarder qu'est-ce qui ce situe dans ton tableau à l'endroit indiqué, mais tu vas remarquer qu'il y a déjà un objet de stocké, mais qu'il est différent. Donc tu vas devoir trouvé un autre emplacement, et ainsi de suite, ce qui peut causer une insertion en O(n) dans le pire des cas. Et donc si tu ajoutes n objets, ça devient O(n²) dans le pire des cas.