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

void formaterVoisinage(liste):

void formaterElement(liste, element):

afficher l’element
POUR CHAQUE élément 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

void formaterElements(liste):

void formaterElement(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