Calculer la complexité d'un algorithme
bonsoir tout le monde, je cherche à savoir la complexité de cet algorithme
Code:
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
| for j := 1 to por do occupe[po[j]] := oc[j];
procedure TForm1.Button4Click(Sender: TObject);
var num_saut, posit: integer;
procedure remplir1;
begin
fillchar(occupe, sizeof(occupe), #0);
end;
procedure sauter(x, numero_saut: integer);
var po: array[1..8] of integer;
oc: array[1..8] of boolean;
i, ii, j, k, m, por, new_x, c: integer;
s1: string;
begin
inc(num_saut);
if numero_saut > 63 then
begin
memo1.lines.clear;
memo1.lines.add('saut=' + inttostr(num_saut));
memo1.lines.add(soluce);
memo1.refresh;
exit;
end;
for i := 1 to nb_sauts[x] do
if not occupe[pos_saut[x] + i - 1] then
begin
c := pos_saut[x] + i - 1;
occupe[c] := true; // si x=1, "occupe[1]:=true" indique : lien "1->11" occupé
new_x := liens[c]; // new_x:=11,18
//--------- on occupe les liens
por := 0;
for j := 1 to 336 do
if liens[j] = new_x then
begin
inc(por);
po[por] := j;
oc[por] := occupe[j];
occupe[j] := true;
end;
//--------- appel récursif
s1 := inttostr(new_x) + ';';
soluce := soluce + s1;
sauter(new_x, numero_saut + 1);
delete(soluce, length(soluce) - length(s1) + 1, length(s1));
//--------- restauration des liens occupées
for j := 1 to por do occupe[po[j]] := oc[j];
occupe[c] := false;
end;
end;
begin // chercher solution
remplir1;
soluce := ''; num_saut := 1;
occupe[2] := true; // on interdit le saut "1->18" car symétrie avec "1->11"
posit := 1;
sauter(posit, 1);
end; |
tout en sachant que nb_saut,pos_saut et liens sont:
nb_sauts: array[1..64] of integer =
(2, 3, 4, 4, 4, 4, 3, 2,
3, 4, 6, 6, 6, 6, 4, 3,
4, 6, 8, 8, 8, 8, 6, 4,
4, 6, 8, 8, 8, 8, 6, 4,
4, 6, 8, 8, 8, 8, 6, 4,
4, 6, 8, 8, 8, 8, 6, 4,
3, 4, 6, 6, 6, 6, 4, 3,
2, 3, 4, 4, 4, 4, 3, 2);
pos_saut: array[1..64] of integer = // pour savoir à quelle position on doit
(1, 3, 6, 10, 14, 18, 22, 25, // chercher la case suivante lors d'un
27, 30, 34, 40, 46, 52, 58, 62, // saut;
65, 69, 75, 83, 91, 99, 107, 113, // on recherche la case suivante dans le
117, 121, 127, 135, 143, 151, 159, 165, // tableau "liens"
169, 173, 179, 187, 195, 203, 211, 217,
221, 225, 231, 239, 247, 255, 263, 269,
273, 276, 280, 286, 292, 298, 304, 308,
311, 313, 316, 320, 324, 328, 332, 335);
liens: array[1..336] of integer =
(11, 18, //----- liens "1->11", "1->18"
12, 17, 19, //----- liens "2->12", "2->17", "2->19"
9, 13, 18, 20,
10, 14, 19, 21,
...
