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 de la liste

int afficherVoisinage(liste):

POUR TOUS les éléments el de la liste:
- afficher cet élément, ainsi que ses voisins
- (appel à afficherElement)

int afficherElement(liste, element):

afficher l’element
POUR TOUS les éléments el de la liste:
- SI el est un voisin de element
  - afficher aussi el

Expliquer votre raisonnement
NOTE: les choix plausibles sont
- O(n): linéaire
- O(n²): quadratique
- O(2ⁿ): exponentiel

Avec la notation O(), indiquer l’efficacité du pseudo-code ci-bas:
- n fait référence à la taille de la liste
- un element a au plus 3 attributs

int afficherElements(liste):

POUR TOUS les éléments el de la liste:
- afficher cet élément
- (appel à afficherElement)

int afficherElement(element):

POUR CHAQUE attribut attr de l’element:
- afficher la valeur de cet attr

Expliquer votre raisonnement
NOTE: les choix plausibles sont
- O(n): linéaire
- O(n²): quadratique
- O(2ⁿ): exponentiel

Avec la notation O(), indiquer l’efficacité du pseudo-code de l’algorithme qui fusionne 2 listes ci-bas:
- n fait référence à la taille de la liste de gauche + la liste de droite

Liste fusionner(Liste listeGauche, Liste listeDroite):

CRÉER une liste resultat vide
INITIALISER les indices i et j à 0
TANT QUE i est < à la taille de listeGauche ET j est < à la taille de listeDroite:
- SI l’élément à l’index i de listeGauche est <= à l’élément à l’index j de listeDroite:
  - ajouter l’élément à l’index i de listeGauche dans resultat
- incrementer i
- SINON:
  - ajouter l’élément à l’index j de listeDroite dans resultat
  - incrementer j
TANT QUE i est inférieur à la taille de listeGauche:
- ajouter l’élément à l’index i de listeGauche dans resultat
- incrementer i
TANT QUE j est inférieur à la taille de listeDroite:
- ajouter l’élément à l’index j de listeDroite dans resultat
- incrementer j
retourner la liste resultat

Expliquer votre raisonnement
NOTE: les choix plausibles sont
- O(n): linéaire
- O(n²): quadratique
- O(2ⁿ): exponentiel