Écrire compte occurrences(t, v) par parcours séquentiel, puis comparer…

def compte_occurrences(t, v):
    """Nombre d'éléments de t égaux à v.

    Postcondition : 0 <= résultat <= len(t).
    """
    n = 0
    for x in t:
        if x == v:
            n = n + 1
    return n

def effectifs(t):
    """Dictionnaire valeur -> nombre d'occurrences (chapitre 5)."""
    d = {}
    for x in t:
        d[x] = d.get(x, 0) + 1
    return d

Validation : sur $2000$ tableaux tirés au hasard, et pour chaque valeur possible, les trois voies — parcours, dictionnaire, t.count(v) — donnent le même nombre.

Le choix, chiffré. Soit $n$ la taille du tableau et $q$ le nombre d'interrogations. Le parcours coûte $n$ par question, soit $n\times q$ en tout ; le dictionnaire coûte $n$ une fois pour le construire, puis une opération par question, soit $n+q$.

La bascule est immédiate. Pour une question, les deux coûtent la même chose — et le parcours est plus simple, donc préférable. Dès deux questions, le dictionnaire gagne. À mille, il fait mille fois moins de travail.

Le raisonnement, plus général que le cas. On compare un coût $nq$ à un coût $n+q$ : c'est le marché « précalculer ou recalculer », déjà rencontré aux sommes préfixes et à la fusion indexée du chapitre 6, et qu'on retrouvera au chapitre 8 avec « trier d'abord, chercher ensuite ». Précalculer paie dès qu'on interroge plusieurs fois. Le seul cas où cela ne paie pas est la question unique — et encore, à condition que la donnée ne resserve pas.