Entrevue 3.3: comprendre l’efficacité #
NOTE: à faire sur papier
Analyse 1 #
- Avec la notation
O()
, indiquer l’efficacité du pseudo-code ci-bas:n
fait référence à la taille du tableau
int afficherVoisinage(tableau)
:
- POUR TOUS les éléments
el
dutableau
:- afficher cet élément, ainsi que ses voisins
- (appel à
afficherElement
)
int afficherElement(tableau, element)
:
- afficher l'
element
- POUR TOUS les éléments
el
dutableau
:- SI
el
est un voisin deelement
- afficher aussi
el
- afficher aussi
- SI
-
Expliquer votre raisonnement
-
NOTE: les choix plausibles sont
O(n)
: linéaireO(n2)
: quadratiqueO(2n)
: exponentiel
Analyse 2 #
- Avec la notation
O()
, indiquer l’efficacité du pseudo-code ci-bas:n
fait référence à la taille du tableau- un
element
a au plus3
attributs
int afficherVoisinage(tableau)
:
- POUR TOUS les éléments
el
dutableau
:- afficher cet élément
- (appel à
afficherElement
)
int afficherElement(element)
:
- POUR CHAQUE attribut
attr
de l'element
:- afficher la valeur de cet
attr
- afficher la valeur de cet
-
Expliquer votre raisonnement
-
NOTE: les choix plausibles sont
O(n)
: linéaireO(n2)
: quadratiqueO(2n)
: exponentiel