Algorithme
Résolu/Fermé
A voir également:
- Algorithme
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Logiciel algorithme euromillion - Télécharger - Loisirs créatifs
- Code ascii algorithme - Guide
- Algorithme maximum de 3 nombres ✓ - Forum Algorithmes / Méthodes
- Tester un algorithme en ligne - Forum Programmation
2 réponses
fiddy
Messages postés
11069
Date d'inscription
samedi 5 mai 2007
Statut
Contributeur
Dernière intervention
23 avril 2022
1 842
3 févr. 2009 à 00:54
3 févr. 2009 à 00:54
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).
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).
fiddy
Messages postés
11069
Date d'inscription
samedi 5 mai 2007
Statut
Contributeur
Dernière intervention
23 avril 2022
1 842
3 févr. 2009 à 01:16
3 févr. 2009 à 01:16
2) Il serait beaucoup plus simple d'écrire: ...
Sauf que ta version n'a rien à voir avec le sien. Le sien renvoie : 1+E(Log2 (n)), avec E la valeur entière.
Sauf que ta version n'a rien à voir avec le sien. Le sien renvoie : 1+E(Log2 (n)), avec E la valeur entière.
loupius
>
fiddy
Messages postés
11069
Date d'inscription
samedi 5 mai 2007
Statut
Contributeur
Dernière intervention
23 avril 2022
3 févr. 2009 à 01:29
3 févr. 2009 à 01:29
Ah ben évidemment que ça n'a rien à voir puisqu'apparemment l'algorithme était faux et que tu l'as corrigé!!!
3 févr. 2009 à 01:16