def vandermonde(n, p):
    M = []
    for i in range(n):
        L = []
        for j in range(p):
            L.append(i∗∗j)
        M.append(L)
    return M

>>> vandermonde(6,4)

L'exécution vandermonde(6,4) produit la réponse [[1, 0, 0, 0], [1, 1, 1, 1], [1, 2, 4, 8], [1, 3, 9, 27], [1, 4, 16, 64], [1, 5, 25, 125]]. Écrit ainsi, on ne voit pas la matrice. Mais on peut écrire la réponse sous une forme plus proche d'une matrice :

[ [1, 0, 0, 0],
  [1, 1, 1, 1],
  [1, 2, 4, 8],
  [1, 3, 9, 27],
  [1, 4, 16, 64],
  [1, 5, 25, 125]]

Du de point de vue du programme, la matrice est un tableau de tableau. C'est à dire que si V = vandermonde(6,4), alors V[2] est la ligne d'indice 2, c'est à dire [1, 2, 4, 8]. On peut donc demander V[2][3] qui vaut 8. La notation V[2, 3] est tentante mais ne sera pas reconnue.

Pour la complexité, comptons rapidement le nombre d'exécution de chaque ligne :

def vandermonde(n, p):        # nombre répétition :
    M = []                    # 1
    for i in range(n):        # n
        L = []                # n
        for j in range(p):    # n * p
            L.append(i∗∗j)    # n * p
        M.append(L)           # n
    return M                  # 1

On a donc un total de 2*n*p + 3*n + 2. Bien sûr, il ne faut pas trop attaché d'importance aux coefficients exacts. L'idée importante est que le cœur de boucle est répété n*p fois.

for i in range(4):
    for j in range(i): # noter le i
        print(i, j)

1 0
2 0
2 1
3 0
3 1
3 2

def tableau_triangulaire(n):
    """
    crée un tableau triangulaire de taille n avec m[i][j]=(i+1)∗(j+1)
    """
    M = []
    for i in range(n):
        L = []
        for j in range(i): # j décrit l'intervalle d'entier [[0 , i−1]]
            item = (i + 1)∗∗(j + 1)
            L.append(item)
        M.append(L)
    return M

>>> tableau_triangulaire(5)

Le tableau obtenu contient moins d'éléments : [[], [2], [3, 9], [4, 16, 64], [5, 25, 125, 625]]

On fera en gros 2 fois moins d'instructions dans cette version que dans la version non triangulaire. Le temps de calcul sera donc 2 fois moindre.

L'occupation en mémoire est également 2 fois moindre. Remarquez néanmoins que la structure de la réponse s'en trouve complexifiée puisque les lignes de ce tableau ont des tailles différentes. Selon le cas, selon la valeur de n, on pourra raisonner ainsi :

• n assez faible – par exemple moins de 100 – le tableau occupe peut de place de toute façon et cela ne change pas grand chose de doubler sa taille. On pourra alors préférer un tableau bien carré quitte à bourré les places inutiles avec des 0.
• n grand – par exemple 1000 ou plus – le tableau est très gourmand et on veillera à ne pas l'augmenter inutilement. On pourra alors garder la forme triangulaire, même si elle occasionne quelques complications de plus, pour réduire autant que possible la consommation d'espace mémoire.