[Vérification] Exercices de complexité
Bonjour,
Dans le cadre de mes études, j'ai à rendre un devoir de complexité et j'avoue que ce n'est pas mon fort. J'ai fait la plus part des exercices (à la rigueur des pistes pour certains) et j'aimerais avoir des avis sur mes réponses.
Le premier exercice demande de donner la compléxité de morceaux de code. Tout d'abord, l'énoncé (en anglais) parle de "computational complexity", est-la notation "grand O" ou bien un calcul plus "exact" du nombre d'opérations effectuées ?
Algorithme 1
Code:
1
2
3
4
5
6
7
8
|
for (int i=n ; i>0 ; i/=2) { Pour moi, log(n) passages
for (int j=1 ; j<n ; j*=2) { Pour moi, log(n-1) passages
for (int k=0 ; k<n ; k+=2) { Pour moi, n/2 passages
// Constant number of operations
}
}
} |
Ici j'ai répondu O(n.log²(n)).
Algorithme 2
Code:
1
2
3
4
5
6
7
8
|
for (int i=1 ; i<n ; i++) { Pour moi, n passages
for (int j=i ; j<n ; j++) { Pour moi, (n-i) passages, au maximum n-1 passages
for (int k=0 ; k<j ; k++) { Pour moi, j passages, au maximum n passages
// Constant number of operations
}
}
} |
Ici j'ai répondu O(n^3).
Algorithme 3
Code:
1
2
3
4
5
6
7
8
|
for (int i=n ; i>0 ; i--) { Pour moi, n passages
for (int j=1 ; j<n ; j*=2) { Pour moi, log(n-1) passages
for (int k=0 ; k<j ; k++) { Pour moi, j passages, au maximum log(n-1) passages
// Constant number of operations
}
}
} |
Ici j'ai répondu O(n.log²(n)).
L'exercice 2 est le suivant :
Citation:
Vous vous trouvez au pied d'un très long mur (comme la grande muraille de chine), vous savez qu'il y a une porte à n kilomètres mais vous ne savez pas si elle est à gauche ou à droite. Montrez qu'il est possible de trouver la porte en marchant au pire Grand Theta(n) kilomètres.
Je n'ai pas véritablement de réponse à celui-ci.
Mon idée d'algorithme serait de marche une certaine distance (laquelle) sur la gauche puis si l'on ne trouve pas la porte, revenir au point de départ et marcher le double à droite, puis le double à gauche, ...
Mais je ne vois vraiment pas comment cela peut se rapprocher des Grand Theta(n) kilomètres.
Merci ^^
