Exercices sur la complexité

Déterminer la complexité des fonctions suivantes :

from typing import List

def surface1(longueur: int, largeur: int) -> int:
    surface = 0
    for i in range(largeur):
        surface += longueur
    return surface

def surface2(longueur: int, largeur: int) -> int:
    surface = longueur * largeur
    return surface

def somme(tab: List[float]) -> float:
    total = 0
    for v in tab:
        total += v
    return total

• Exécuter la fonction mystere(), puis déterminer sa complexité.
• Expliquer l’instruction assert nbessais <= 7 puis corriger le programme pour faire deviner un nombre entre 1 et 4000.

def mystere():
    nbmyst = int(input("Choisi un nombre entre 1 et 100 : "))
    assert nbmyst >= 1 and nbmyst <= 100
    inf = 1; sup = 100; prop = 0; nbessais = 0
    while prop != nbmyst and inf < sup:
        nbessais += 1
        prop = (inf + sup) // 2 #l'ordinateur ne triche pas…
        rep = input("Est-ce " + str(prop) + " ? [=/+/-] : ")
        if rep == "+":
            inf = prop + 1
        elif rep == "-":
            sup = prop
    print("Nombre d'essais : " + str(nbessais))
    assert nbessais <= 7