Complexité algorithmique des Courbes de Hilbert [Résolu]

[alexgille]

Bonjour,

j'ai cet algorithme des Courbes de Hilbert :

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
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]

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

[alexgille]

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]

(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]

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

[Franck Dernoncourt]

Envoyé par alexgille

peut-on dire que O(4^n) est équivalent à O(2^n) ? Est-ce une aberration? :p

Une aberration
(car la limite de 4^n / 2^n tend vers +infini lors n tend vers +infini)

[aymenbech]

Salut
pour cet algorithme de Hilbert , comment l'utiliser pour parcourir une image
( Au lieu de parcourir l'image horizontalement je veux la parcourir a l'aide de la courbe de Hilbert) pouvez vous m'aider ? et merci

[alexgille]

Tu devrais poser ta question dans un nouveau topic, plus de gens pourrait t'aider.

Pour le parcours d'image avec Hilbert je ne connais pas trop. Toutefois:
Les courbes de Hilbert fonctionnent comme ceci:
Tu prend un carré, tu le divise en 4 sous-carrés, ainsi de suite jusqu'à obtenir autant de sous-carrés de sous-carrés de sous-carrés qu'il n'en faut pour calculer ta courbe au rang voulu. Puis tu parcours ta matrice ainsi formée en reliant les centres de chacun des petits carrés obtenus.

Dans ton cas, ton image est une matrice, et le chemin de passage que représente la courbe de Hilbert est la façon dont tu dois lire les pixels de ton image (donc les cases de ta matrice).

Sur internet il y a des algorithmes expliqués pour cela.