Algorithme
Résolu
anonyme-113
-
loupius -
loupius -
Bonjour,
Soit l'algorithme suivant :
Int F(int n)
{
Int k = 0 ;
For (int i=1 ; i<n ; i=2*n)
k++;
return k;
}
Je cherche comment on peut démontrer qu'il est de compléxité de Ө(log n).
Merci d'avance.
Soit l'algorithme suivant :
Int F(int n)
{
Int k = 0 ;
For (int i=1 ; i<n ; i=2*n)
k++;
return k;
}
Je cherche comment on peut démontrer qu'il est de compléxité de Ө(log n).
Merci d'avance.
A voir également:
- Algorithme
- Logiciel algorithme euromillion - Télécharger - Loisirs créatifs
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Algorithme euromillion excel gratuit - Forum Algorithmes / Méthodes
- Algorithme ajout rapide snapchat - Forum Snapchat
- Ajout rapide snap - Forum Snapchat
2 réponses
Salut,
Je pense que tu voulais dire : For (int i=1 ; i<n ; i=2*i)
La variable i sera multiplié par 2 à chaque itération. Ainsi i vaudra 2^(k-1) à la kème itération (k est la complexité de l'algo).
Il faut i < n. Donc 2^(k-1)<n avec k sa complexité. On peut enlever le 1, puisque négligeable devant k.
Et on trouve que la complexité est de : log(n) (log base 2).
Je pense que tu voulais dire : For (int i=1 ; i<n ; i=2*i)
La variable i sera multiplié par 2 à chaque itération. Ainsi i vaudra 2^(k-1) à la kème itération (k est la complexité de l'algo).
Il faut i < n. Donc 2^(k-1)<n avec k sa complexité. On peut enlever le 1, puisque négligeable devant k.
Et on trouve que la complexité est de : log(n) (log base 2).
anonyme-113
oui, c'est exactement ça , merci pour ta reponse fiddy
1) Pour moi, il ne s'agit pas d'un algorithme mais d'un programme!
2) Il serait beaucoup plus simple d'écrire:
Soit l'algorithme suivant :
Je cherche comment on peut démontrer qu'il est de compléxité de Ө(log n).
2) Il serait beaucoup plus simple d'écrire:
Int F(int n)
{
return 1;
}3) Je ne vois pas ce que vient faire le 'log'. Pour moi la complexité est '1', mais je n'en mettrais pas ma main à couper!
Soit l'algorithme suivant :
Je cherche comment on peut démontrer qu'il est de compléxité de Ө(log n).
