Parcours et complexité

Boucles imbriquées et O(n×p)

← Retour au cours Tableaux 2D

Somme d'une matrice

O(n×p)

Boucle externe sur les lignes, interne sur les colonnes.

nb_lignes = len(matrice)
Hauteur
nb_colonnes = len(matrice[0])
Largeur
somme += matrice[i][j]
Accès O(1) par case
Complexité
O(nb_lignes × nb_colonnes)

Maximum d'une image

max

Parcourir toutes les cases pour le pixel le plus lumineux.

pixel_max = image[0][0]
Initialisation
for ligne in range(hauteur):
Parcours lignes
for colonne in range(largeur):
Parcours colonnes
Comparaison
Mettre à jour pixel_max

💻 Exemples de code

Somme d'une matrice

somme_matrice.py 
def somme_matrice(matrice):
    somme = 0
    nb_lignes = len(matrice)
    nb_colonnes = len(matrice[0])
    for ligne in range(nb_lignes):
        for colonne in range(nb_colonnes):
            somme += matrice[ligne][colonne]
    return somme

Maximum d'une image (niveaux de gris)

max_image.py 
def luminosite_max(image):
    pixel_max = image[0][0]
    hauteur = len(image)
    largeur = len(image[0])
    for ligne in range(hauteur):
        for colonne in range(largeur):
            if image[ligne][colonne] > pixel_max:
                pixel_max = image[ligne][colonne]
    return pixel_max

📋 Aide-mémoire

Tenseur (aperçu)

Rang 0 = scalaire, 1 = vecteur, 2 = matrice, 3 = volume (RGB).

Rotation 90° : nouvelle matrice sans aliasing ; indices (i,j) → (j, H−1−i).