Discussion :

[laureat]

Salut,
Quelle est la complextité ce t algorithme?
Moi, je dirais O(n), est ce je me trompe?
Par avance, merci!

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
typedef int (*compfn) (const void *, const void *);
 
struct tache
{
  int release_date;
  int duree;
  int due_date;
  int id_tache;
};
 
typedef struct
{
  int date_disponibilite;
}
machine;
 
struct tache job[] = {
  {3, 0, 4, 1}, {5, 3, 5, 2}, {1, 4, 12, 3}, {2, 7, 10, 4}, {4, 8, 11, 5}
};
/*fonction tri par ordre croissant de sa date de fin*/
int compare (struct tache *elem1, struct tache *elem2)
{
  if (elem1->due_date < elem2->due_date)
      return -1;
  else if (elem1->due_date > elem2->due_date)
      return 1;
  else
      return 0;
}
 
void printarray (void)
{
  int i;
 
  for (i = 0; i < 5; i++)
      printf ("  %d ", job[i].id_tache);
 
}
 
int main (void)
{
  float temps;
  clock_t t1 = clock (), t2;
  machine Machines[3];
  int id_machineDispo;
  int retardsTotaux = 0;
  int retards, j, k;
 
  qsort ((void *) &job, 5, sizeof (struct tache), (compfn) compare);
  printf ("\n due_date tache par ordre croissant\n");
  printarray ();
  printf ("\n");
 
  for (j = 0; j < 3; j++)
  {
      Machines[j].date_disponibilite = 0;
  }
  /* pour toute les taches */
  for (k = 0; k < 5; k++)
  {
 
      id_machineDispo = 0;
 
      /* trouver la machine disponible plus tot */
      for (j = 0; j < 3; j++)
      {
        if (Machines[j].date_disponibilite <
            Machines[id_machineDispo].date_disponibilite)
 
            id_machineDispo = j;
 
      }
 
      /* calculer date fin tache sur machine */
      if (k < 3)
 
        Machines[id_machineDispo].date_disponibilite +=
            job[k].duree + job[k].release_date;
 
      if (k >= 3)
 
        Machines[id_machineDispo].date_disponibilite += job[k].duree;
 
      /* affichage affectation */
      printf ("\n date disponibilite  machine %d egale : %d ",
              id_machineDispo, Machines[id_machineDispo].date_disponibilite);
      printf ("\n placer tache %d sur machine %d", job[k].id_tache,
              id_machineDispo);
      printf ("\n");
      /* calcul retard et retards totaux */
      retards =
        Machines[id_machineDispo].date_disponibilite - job[k].due_date;
      printf ("\n retards : %d", retards);
      printf ("\n");
      if (retards > 0)
        retardsTotaux += retards;
 
      /* affichage retards totaux */
      printf ("\n retards totaux : %d\n", retardsTotaux);
  }
  t2 = clock ();
  temps = (float) (t2 - t1) / CLOCKS_PER_SEC;
  /* temps exécution application */
  printf ("temps = %f\n", temps);
 
  return 0;
}

[souviron34]

déjà qsort est en N*log(N)

[laureat]

et donc c'est N+N LOG N

[sopsag]

Quand on résonne avec O ("grand o"), O( n + n.log n ) c'est pareil que O( n.log n ).
Mais ça c'est la théorie...
Le O, ça n'a de sens que sur des très grandes valeurs.

Juste pour donner un exemple :
- quick sort est en O( n.log n ) en moyenne et en O( n² ) au pire.
- heap sort est en O( n.log n ) en moyenne ET au pire.
Du coup on pourrait toujours choisir heap sort mais en pratique, à moins d'avoir des milliards d'éléments, quick sort est toujours + rapide.

Dans ton exemple, à moins d'avoir beaucoup d'éléments (ce qui ne semble pas être le cas, vue ta déclaration du tableau "job"), rien que les "printf" vont prendre + de temps que le qsort.

Donc, calculer la complexité d'un tri ou d'un parcours de tableau, à moins de faire des opérations sur des bases de données monstrueuses ou d'avoir un devoir à rendre, ça ne sert pas à grand chose...

Si tu écris des algos de théorie des graphes, tu peux être amené à te poser ce genre de questions, parce là, même avec un petit millier d'éléments, tu peux tomber sur une explosion combinatoire qui t'obligera à changer d'approche... et à considérer les questions de complexité.

Voilà, j'espère que mon long discourt t'aura été de quelque utilité.

[laureat]

Merci pour ces explication sopsag!
Ca me serait très utile!
Encore, merci beaucoup!