la recherche d'un élément x dans une liste est linéaire ( de l'ordre de n ) et non pas n^2 ( on parcout la liste une seule fois , donc le pire des cas , on fait n tests )
En fait, ceci n'est qu'une théorie personnelle, mais je crois que le résultat exprimé dans la vidéo est en effet juste. Cela est du à la boucle "jusqu'à" qui est utilisée car elle force à compter le nombre d'éléments dans la liste. Par contre, habituellement, lorsque l'on fait une recherche séquentielle, on a tendance à connaitre le nombre d'éléments figurant dans la liste avant de commencer. Cela permet d'alléger la tâche du processeur.
excellente vidéo et merci. sinon j'ai deux(2) questions, la condition de la boucle(i>taille(L)) ne sera pas exécuté n+1 fois? différemment du contenu de la boucle qui est exécuté n fois(biensure dans le pire des cas, ou l'on ne trouve pas l'élément dans le tableau) et pourquoi n'avez vous pas calculé(toujours pour i>taille(L)) l'exécution du comparateur(>) et l'exécution de la taille(c.-à-d. 1 +1) comme fait dans l'algorithme 2
n*2 est du à la fonction taille(l) car elle effectue n opération pour savoir la taille il a dit justement. du coup sa fait qu'il va répéter les 2 opération + taille(l) qui fait n opération, n fois. ce qui fait n*2 + 2n
il a utilisé dans le premier algorithme un boucle while.. Traduit cette écriture algorithmique en un langage de programmation C ou python ou n'importe quel langage , tu pourras alors déduire comment il l'a trouvé ;)
Pour calculer la complexité d'un algo il faut d'abord calculer le nombre d'opérations élémentaire. D'après le premier exemple R1 tu n'as pas pris en considération pour le calcul de la complexité, la consultation d'un élément dans un tableau et opération arithmétique
Slt à vous, merci pr vos explications.Concernant le calcul du R2: Vous dites q l'exécution de: pour i allant se 1 à t {si x=L(i)..} comment il en resulte:...n(2).. alors q l calcul à R1 ns avions l'execution similaire c'est-à-dire : ..si x= L(i)...: et ici il en resulte 1 comme execussion? Merci
Je ne suis pas sûr d'avoir compris votre question, mais je tente : la différence entre les deux cas est la suivante : si l'on regarde le pire cas imaginable dans R1, il faudra atteindre i = taille(L). Le problème dans cet algorithme est qu'a chaque fois que la boucle se répète, il faut recalculer la taille(L) et vu qu'on est dans le pire cas possible, la boucle se répétera un nombre de fois égal à taille(L). Ainsi, on a taille(L)*taille(L) (=> taille(L)^2) ce qui est représenté par le n^2.
Emma Tjepkema merci, c'est en lisant ce commentaire que je suis parvenu à comprendre la R1, j'avais pas compris pourquoi on a mis un n pour l'instruction de jusqu'à, en effet dans la vidéo l'omission du mot "recalcul" de la taille de la liste s'est fait sentir
Je suis avec; pour quoi vous avez comptez dans R1 "x=L(i)" comme une seule opération, par contre dans R2 vous avez comptez comme 2 opérations ((x = ...) et (L(i))) => normalement 1 se qui donne Rc2 = n + n(1) = 2n ? Merci pour cette vidéo.
quell eat la complexite de ce algorithme import javax.swing.*; import java.awt.*; import java.awt.event.MouseAdapter; import java.awt.event.MouseEvent; public class hanoi { static int s=1; static int n; public static void hanoi(int n, String from, String temp, String to) { if (n == 0) return; hanoi(n-1, from, to, temp); System.out.println("Step "+(s++)+ " : Move the disc " + n + " from " + from + " to " + to ); hanoi(n-1, temp, from, to);
} public static void main(String[] args) { JFrame f = new JFrame("Honoi"); JPanel p = new JPanel(); JPanel p1 = new JPanel(); JPanel p2 = new JPanel(); JPanel p3 = new JPanel(); JPanel p4 = new JPanel(); JPanel p5 = new JPanel(); JLabel g1 = new JLabel(" how mach disc ="); JLabel g = new JLabel(" HONOI"); JButton b = new JButton("OK"); JButton b1 = new JButton("Quit"); JTextField t = new JTextField(); p.setLayout(new BorderLayout()); p1.setLayout(new BorderLayout()); p2.setLayout(new BorderLayout()); p3.setLayout(new BorderLayout()); p4.setLayout(new BorderLayout()); p5.setLayout(new BorderLayout());
Excellente vidéo. Simple et didactique. Merci.
Très bien expliqué, merci.
Merci beaucoup !
merci roulhya
la recherche d'un élément x dans une liste est linéaire ( de l'ordre de n ) et non pas n^2 ( on parcout la liste une seule fois , donc le pire des cas , on fait n tests )
En fait, ceci n'est qu'une théorie personnelle, mais je crois que le résultat exprimé dans la vidéo est en effet juste. Cela est du à la boucle "jusqu'à" qui est utilisée car elle force à compter le nombre d'éléments dans la liste. Par contre, habituellement, lorsque l'on fait une recherche séquentielle, on a tendance à connaitre le nombre d'éléments figurant dans la liste avant de commencer. Cela permet d'alléger la tâche du processeur.
pour répondre à ta question, la complexité dépend de l'algorithme utilisé pour ressourdre un problème et non du problème à ressourdre
excellente vidéo et merci. sinon j'ai deux(2) questions, la condition de la boucle(i>taille(L)) ne sera pas exécuté n+1 fois? différemment du contenu de la boucle qui est exécuté n fois(biensure dans le pire des cas, ou l'on ne trouve pas l'élément dans le tableau) et pourquoi n'avez vous pas calculé(toujours pour i>taille(L)) l'exécution du comparateur(>) et l'exécution de la taille(c.-à-d. 1 +1) comme fait dans l'algorithme 2
le test de (i< taille de tab) sera répété 1 fois à chaque iteration alors ça va donner n , non pas n*2 et merci
n*2 est du à la fonction taille(l) car elle effectue n opération pour savoir la taille il a dit justement. du coup sa fait qu'il va répéter les 2 opération + taille(l) qui fait n opération, n fois. ce qui fait n*2 + 2n
Bonjour,
Dans R1(x,L)
Comment transformez-vous ?
1 + (1 + 1 + n) n
Je devine que cela represente les deux boucles ?
n2 + 2n + 1
Merci
oui , je suis d'accord avec vous
il a utilisé dans le premier algorithme un boucle while.. Traduit cette écriture algorithmique en un langage de programmation C ou python ou n'importe quel langage , tu pourras alors déduire comment il l'a trouvé ;)
Merci !
vous êtes sûr qu'avec ça un élève moyen peut comprendre la notion de complexité
Non toujours pas ça a toujours été du chinois pour moi
Pour calculer la complexité d'un algo il faut d'abord calculer le nombre d'opérations élémentaire. D'après le premier exemple R1 tu n'as pas pris en considération pour le calcul de la complexité, la consultation d'un élément dans un tableau et opération arithmétique
Exactement c'est ce pourquoi je suis venu dans les commentaires pour voir si quelqu'un a remarque la meme chose
5:25 s'il vous plait j'ai pas compris pourquoi t'as mis n en principe c'est une affectation , on doit alors mettre 1 non ?
C'est parce qu'il compte la fonction taille(l) qui fait n opération pour savoir la taille. D’ailleurs au R1 il a aussi compter la fonction taille(l)
La complexité pour une recherche dans une liste est linéaire au départ.
Slt à vous, merci pr vos explications.Concernant le calcul du R2: Vous dites q l'exécution de: pour i allant se 1 à t {si x=L(i)..}
comment il en resulte:...n(2).. alors q l calcul à R1 ns avions l'execution similaire c'est-à-dire : ..si x= L(i)...: et ici il en resulte 1 comme execussion?
Merci
+Na P oui c est ça ce que j ai pas compris :(
Je ne suis pas sûr d'avoir compris votre question, mais je tente : la différence entre les deux cas est la suivante : si l'on regarde le pire cas imaginable dans R1, il faudra atteindre i = taille(L). Le problème dans cet algorithme est qu'a chaque fois que la boucle se répète, il faut recalculer la taille(L) et vu qu'on est dans le pire cas possible, la boucle se répétera un nombre de fois égal à taille(L). Ainsi, on a taille(L)*taille(L) (=> taille(L)^2) ce qui est représenté par le n^2.
Emma Tjepkema merci, c'est en lisant ce commentaire que je suis parvenu à comprendre la R1, j'avais pas compris pourquoi on a mis un n pour l'instruction de jusqu'à, en effet dans la vidéo l'omission du mot "recalcul" de la taille de la liste s'est fait sentir
Je suis avec; pour quoi vous avez comptez dans R1 "x=L(i)" comme une seule opération, par contre dans R2 vous avez comptez comme 2 opérations ((x = ...) et (L(i))) => normalement 1 se qui donne Rc2 = n + n(1) = 2n ? Merci pour cette vidéo.
Pas bien compris le cas de CR1(n)
j ai rien compris
quell eat la complexite de ce algorithme
import javax.swing.*;
import java.awt.*;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
public class hanoi {
static int s=1;
static int n;
public static void hanoi(int n, String from, String temp, String to) {
if (n == 0) return;
hanoi(n-1, from, to, temp);
System.out.println("Step "+(s++)+ " : Move the disc " + n + " from " + from + " to " + to );
hanoi(n-1, temp, from, to);
}
public static void main(String[] args) {
JFrame f = new JFrame("Honoi");
JPanel p = new JPanel();
JPanel p1 = new JPanel();
JPanel p2 = new JPanel();
JPanel p3 = new JPanel();
JPanel p4 = new JPanel();
JPanel p5 = new JPanel();
JLabel g1 = new JLabel(" how mach disc =");
JLabel g = new JLabel(" HONOI");
JButton b = new JButton("OK");
JButton b1 = new JButton("Quit");
JTextField t = new JTextField();
p.setLayout(new BorderLayout());
p1.setLayout(new BorderLayout());
p2.setLayout(new BorderLayout());
p3.setLayout(new BorderLayout());
p4.setLayout(new BorderLayout());
p5.setLayout(new BorderLayout());
p.add(g,BorderLayout.NORTH);
p.add(p2,BorderLayout.CENTER);
p2.add(p5,BorderLayout.CENTER);
p5.add(p1,BorderLayout.SOUTH);
p1.add(g1,BorderLayout.CENTER);
p1.add(t,BorderLayout.SOUTH);
p.add(p3,BorderLayout.AFTER_LAST_LINE);
p3.add(b1,BorderLayout.AFTER_LAST_LINE);
p3.add(b);
b.addMouseListener(new MouseAdapter(){
public void mouseClicked(MouseEvent e){
n=Integer.valueOf(t.getText());
hanoi(n, "A", "B", "C");
}
}
);
b1.addMouseListener(new MouseAdapter(){
public void mouseClicked(MouseEvent e){
System.exit(0);
}
}
);
f.setContentPane(p);
f.setSize(400,200);
f.setVisible(true);
}
}
C'est pas bien expliqué.
Tin cette video aussi elle est pas clair
j'ai rien compris
tres mal expliqué et merci
Du n'importe quoi!!!
c'est faux !!!!
Merci beaucoup !