Ctrl+K

On parle de complexité

On parle de complexité#

L’objectif est de compter le nombre d’instructions réalisées dans un script Python.

Algorithme 1#

1def algo_1(tableau):
2    a = 0
3    for i in range(len(tableau)):
4        a = a + tableau[i]
5    return a

  1. On réalise en console l’appel :

    >>> algo_1([7,3,8,4,9,5])

    • Combien de fois l’instruction en ligne 4 est-elle réalisée ?

    • Quelle est la valeur renvoyée par la fonction ?

  2. On réalise un nouvel appel en console:

    >>> algo_1([i**2 for i in range(100)])

    • Combien de fois l’instruction en ligne 4 est-elle réalisée ?

    • Quelle est la valeur renvoyée par la fonction ?

  3. De façon générale, quel lien existe-t-il entre le tableau et le nombre d’exécutions de l’instruction en ligne 4 ?

Algorithme 2#

1def algo_2(tableau,valeur):
2    a = 0
3    for i in range(len(tableau)):
4        if tableau[i] <= valeur:
5            a = a + 1
6    return a

  1. On réalise en console l’appel :

    >>> algo_2([7,3,8,4,9,5],6)

    • Combien de fois l’instruction en ligne 4 est-elle réalisée ?

    • Quelle est la valeur renvoyée par la fonction ?

  2. On réalise un nouvel appel en console:

    >>> algo_2([i**2 for i in range(100)],1000)

    • Combien de fois l’instruction en ligne 4 est-elle réalisée ?

    • Quelle est la valeur renvoyée par la fonction ?

  3. De façon générale, quel lien existe-t-il entre le tableau et le nombre d’exécutions de l’instruction en ligne 4 ?

Algorithme 3#

1def algo_3(tableau,valeur):
2    i = 0
3    a= 0
4    while tableau[i] <= valeur:
5        a = i
6        i = i + 1
7    return a

  1. On réalise en console l’appel :

    >>> algo_3([7,3,8,4,9,5],6)

    • Combien de fois les instructions aux lignes 4 et 5 sont-elles réalisées ?

    • Quelle est la valeur renvoyée par la fonction ?

  2. On réalise un nouvel appel en console:

    >>> algo_3([i**2 for i in range(100)],10000)

    • Combien de fois les instructions aux lignes 4 et 5 sont-elles réalisées ?

    • Quelle est la valeur renvoyée par la fonction ?

  3. De façon générale, quel lien existe-t-il entre le tableau et le nombre d’exécutions des instructions aux lignes 4 et 5 ?

Algorithme 4#

1def algo_4(tableau):
2    a = 0
3    for i in range(len(tableau)):
4        for j in range(len(tableau[i])):
5            a = a + tableau[i][j]
6    return a

  1. On réalise en console l’appel :

    >>> algo_4([[7,3,8],[4,9,5],[1,2,6]])

    • Combien de fois l’instruction en ligne 5 est-elle réalisée ?

    • Quelle est la valeur renvoyée par la fonction ?

  2. On réalise un nouvel appel en console:

    >>> algo_4([ [i for i in range(j,j+10)] for j in range(10)])

    • Combien de fois l’instruction en ligne 5 est-elle réalisée ?

    • Quelle est la valeur renvoyée par la fonction ?

  3. De façon générale, quel lien existe-t-il entre le tableau et le nombre d’exécutions de l’instruction à la ligne 5 ?

Contenu