Complexité algorithmique des Courbes de Hilbert

**alexgille** · 26/12/2011, 18h57

Bonjour,

j'ai cet algorithme des Courbes de Hilbert :

Code Java :

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
private static final long serialVersionUID = 1L;
    private int level;
    private double h;
    private double x;
    private double y;
 
    public MyJPanel(int niveau) {
        super();        
        this.level = niveau;
        this.setVisible(true);
    }
 
    public void paintComponent(Graphics g) {
        super.paintComponents(g);
        init(g);
    }
 
    public void deplacement(Graphics g, int vx, int vy) {
        double ax = x;
        double ay = y;
        x = x + h * vx;
        y = y + h * vy;
        g.drawLine((int) ax, (int) ay, (int) x, (int) y);
    }
 
    public void A(Graphics g, int n) {
        if (n > 0) {
            D(g, n - 1);
            deplacement(g, -1, 0);
            A(g, n - 1);
            deplacement(g, 0, 1);
            A(g, n - 1);
            deplacement(g, 1, 0);
            B(g, n - 1);
        }
    }
 
    public void B(Graphics g, int n) {
        if (n > 0) {
            C(g, n - 1);
            deplacement(g, 0, -1);
            B(g, n - 1);
            deplacement(g, 1, 0);
            B(g, n - 1);
            deplacement(g, 0, 1);
            A(g, n - 1);
        }
    }
 
    public void C(Graphics g, int n) {
        if (n > 0) {
            B(g, n - 1);
            deplacement(g, 1, 0);
            C(g, n - 1);
            deplacement(g, 0, -1);
            C(g, n - 1);
            deplacement(g, -1, 0);
            D(g, n - 1);
        }
    }
 
    public void D(Graphics g, int n) {
        if (n > 0) {
            A(g, n - 1);
            deplacement(g, 0, 1);
            D(g, n - 1);
            deplacement(g, -1, 0);
            D(g, n - 1);
            deplacement(g, 0, -1);
            C(g, n - 1);
        }
    }
 
    public void init(Graphics g) {
        int adiviser = 1;
        if (level > 1) {
            adiviser = (int) (Math.pow(2, level)) - 1;
        }
 
        if (this.getWidth() > this.getHeight()) {
            h = (this.getHeight() - 20) / adiviser;
            x = this.getWidth() / 2 + this.getHeight() / 2;
            y = 10;
        } else {
            h = (this.getWidth() - 20) / adiviser;
            x = this.getWidth() - 10;
            y = this.getHeight() / 2 - this.getWidth() / 2;
        }
        A(g, level);
    }

Seulement je n'arrive pas à déterminer sa complexité. Quelqu'un pourrait-il m'aider ?

Merci beaucoup.

**Franck Dernoncourt** · 26/12/2011, 20h29

J'ai survolé le code (30 secondes), mais ça me semble être du T(n) = 4T(n-1) non ?

**alexgille** · 31/12/2011, 06h55

Mais si on a du T(n) = 4T(n-1), on a donc du O(1) non? Hors ça me parait faux pour cet algorithme ..

**Franck Dernoncourt** · 31/12/2011, 12h35

(T(n) = 4T(n-1) et T(1) = O(1)) => T(n) = O(4^n)

Il suffit de dessiner l'arbre des appels pour voir cela (ici T(n) = 2T(n-1)) :

**alexgille** · 10/01/2012, 20h35

Effectivement ça parait beaucoup plus simple vu comme cela.
Dernière question : peut-on dire que O(4^n) est équivalent à O(2^n) ? Est-ce une aberration? :p

Merci beaucoup pour ton aide