Recherche séquentielle et dictionnaires

L'invariant ${\mathcal{I}}_i$ : « $v\notin \{t[0],\dots ,t[i-1]\}$ » est vrai initialement (préfixe vide) et conservé : on n'atteint le tour $i+1$ que si le test t[i] == v a échoué, ce qui étend l'invariant d'une case. Deux sorties possibles. Si la fonction renvoie $i$ : alors $t[i]=v$ et, par l'invariant, aucun indice plus petit ne convient — c'est bien le plus petit indice. Si la boucle s'achève : ${\mathcal{I}}_n$ dit que $v$ n'apparaît nulle part, et None est conforme au contrat. La terminaison est acquise (boucle for).

(a) Deux accès et une addition : $O(1)$, quel que soit $n$ — t[-1] désigne la dernière case (l'indexation négative est une commodité Python, hors annexe du programme).

(b) Un parcours, chaque tour en $O(1)$ : $O(n)$ — le test if ne change rien à l'asymptotique, il borne juste le travail de chaque tour.

(c) Le piège : x in t est une recherche séquentielle, $O(n)$ à chaque tour. Au total $n\times O(n)=O(n^2)$ : quadratique — pour calculer ce qui vaut toujours len(t) ! (Un coût se lit en multipliant le nombre de tours par le coût d'un tour, en n'oubliant aucun parcours caché.)

On parcourt tout le tableau en retenant la dernière position vue :

def derniere_occurrence(v, t: list):
    pos = None
    for i in range(len(t)):
        # Invariant : pos est le plus grand indice j < i tel que t[j] == v,
        #             ou None si v est absent de t[0..i-1]
        if t[i] == v:
            pos = i
    return pos

L'invariant est conservé : si $t[i]=v$, le plus grand indice devient $i$ ; sinon il ne change pas. À la sortie ($i=n$), pos est le plus grand indice de tout le tableau, ou None. Coût : $O(n)$, et l'on ne peut pas s'arrêter plus tôt — contrairement à la première occurrence, la dernière exige d'avoir tout vu (une occurrence pourrait se cacher dans la partie non lue). (Parcourir à l'envers et s'arrêter à la première trouvaille est l'alternative : même pire cas $O(n)$, mais meilleur cas $O(1)$.)

def frequences(s: str) -> dict:
    """Renvoie {caractère: nombre d'apparitions dans s}."""
    f = {}
    for c in s:
        f[c] = f.get(c, 0) + 1
    return f

f = frequences("abracadabra")
# f == {'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1}
plus_frequent = None
for c in f:
    if plus_frequent is None or f[c] > f[plus_frequent]:
        plus_frequent = c
# plus_frequent == 'a'

Deux étages, tous deux linéaires : le comptage parcourt les $n$ caractères ($O(n)$), la recherche du maximum parcourt les clés du dictionnaire — au plus $n$, donc $O(n)$ aussi. (C'est le « maximum » du début du chapitre, appliqué non plus à un tableau mais aux clés d'un dictionnaire : les algorithmes se composent.)

On maintient le maximum courant et la liste de ses positions ; un nouveau champion remet la liste à zéro :

def indices_du_maximum(t: list) -> list:
    """Précondition : t non vide."""
    m, pos = t[0], [0]
    for i in range(1, len(t)):
        # Invariant : m = max(t[0..i-1]) et pos = liste des j < i avec t[j] == m
        if t[i] > m:
            m, pos = t[i], [i]      # nouveau maximum : on repart de lui seul
        elif t[i] == m:
            pos.append(i)           # une position de plus pour le même maximum
    return pos

assert indices_du_maximum([3, 7, 1, 7]) == [1, 3]
assert indices_du_maximum([5]) == [0]
assert indices_du_maximum([2, 2, 2]) == [0, 1, 2]

La subtilité est la remise à zéro pos = [i] : les anciennes positions concernaient un maximum désormais battu, elles ne valent plus rien. Coût $O(n)$. (Trois branches — strictement plus grand, égal, plus petit — et chacune mérite son test : c'est le tri des cas du chapitre 1 en action.)

Le comptage par dictionnaire donne tout en deux parcours linéaires :

def majoritaire(t: list):
    c = {}
    for x in t:                    # passage 1 : compter
        c[x] = c.get(x, 0) + 1
    for v in c:                    # passage 2 : chercher un compte > n/2
        if c[v] > len(t) / 2:
            return v
    return None

assert majoritaire([2, 5, 2, 2]) == 2
assert majoritaire([2, 5, 2, 5]) is None    # 2 fois sur 4 : pas STRICTEMENT plus de n/2
assert majoritaire([]) is None

Coût : $O(n)+O(n)=O(n)$. La version sans dictionnaire — pour chaque élément, compter ses occurrences par un parcours — coûterait $O(n^2)$ : le dictionnaire divise le travail par un facteur $n$. (Au plus un élément peut être majoritaire — deux comptes ne peuvent excéder $n/2$ chacun — c'est pourquoi renvoyer le premier trouvé est correct.)

def inverse(annuaire: dict) -> dict:
    """Précondition : les valeurs de annuaire sont deux à deux distinctes."""
    qui = {}
    for nom in annuaire:
        qui[annuaire[nom]] = nom
    return qui

def inverse_multi(annuaire: dict) -> dict:
    """Version générale : numéro -> liste des noms (sans précondition)."""
    qui = {}
    for nom in annuaire:
        num = annuaire[nom]
        if num not in qui:
            qui[num] = []
        qui[num].append(nom)
    return qui

Coût $O(n)$ pour $n$ entrées dans les deux cas. La première version exige sa précondition : si deux noms partagent un numéro, l'écriture qui[num] = nom écrase silencieusement le premier — une erreur de logique sans aucun message, exactement le scénario contre lequel le chapitre 1 mettait en garde. La version multi remplace l'écrasement par l'accumulation dans une liste. (L'idiome « si la clé est neuve, créer une liste vide, puis ajouter » est le second réflexe-dictionnaire à connaître, après le comptage.)

L'idée : pour chaque $x$ rencontré, le partenaire idéal est $\text{cible}-x$ ; un dictionnaire mémorise les valeurs déjà vues pour interroger le passé en $O(1)$ :

def deux_sommes(t: list, cible: float) -> bool:
    vus = {}
    for x in t:
        # Invariant : vus contient exactement les valeurs de la partie déjà parcourue
        if (cible - x) in vus:
            return True
        vus[x] = True
    return False

assert deux_sommes([3, 8, 2, 5], 10) == True      # 8 + 2
assert deux_sommes([3, 8, 2, 5], 4) == False
assert deux_sommes([5, 5], 10) == True            # deux indices distincts, valeurs égales
assert deux_sommes([5], 10) == False              # un seul 5 : pas de paire

Chaque tour effectue un test d'appartenance et une insertion, tous deux $O(1)$ : total $O(n)$. La version naïve à deux boucles imbriquées (tester tous les couples) coûte $O(n^2)$ — le chapitre 3 lui est consacré. Noter que l'invariant règle finement le cas $[5]$ avec cible $10$ : quand on examine $x=5$, le dictionnaire ne contient que le passé strict, donc pas $x$ lui-même — les deux indices sont automatiquement distincts. (Interroger « le passé » mémorisé dans un dictionnaire plutôt que re-parcourir : c'est le geste qui fait tomber un facteur $n$.)

Compte de la version du cours : l'initialisation coûte une comparaison ; chacun des $n-2$ tours coûte une comparaison si $t[i]>m_1$, deux sinon. Le pire cas — par exemple un tableau où presque aucun élément ne bat $m_1$ — donne $1+2(n-2)=2n-3$ comparaisons.

Le tournoi : faire s'affronter les éléments deux à deux comme dans une coupe — $n-1$ matchs désignent le champion $m_1$. Observation clé : le second maximum a nécessairement perdu contre le champion (sinon, qui l'aurait éliminé ?). Or le champion n'a disputé que $\lceil {\log }_{2}n\rceil$ matchs (un par tour de la coupe) : il suffit de chercher le maximum parmi ses $\lceil {\log }_{2}n\rceil$ victimes, soit $\lceil {\log }_{2}n\rceil -1$ comparaisons de plus. Total : $n+\lceil {\log }_{2}n\rceil -2\approx n+{\log }_{2}n$, contre $2n-3$. Pour $n=10^6$ : environ $1000018$ comparaisons au lieu de $1999997$ — presque deux fois moins. (Les deux algorithmes restent $O(n)$ : l'asymptotique ne voit pas la différence, mais le compte exact des comparaisons, lui, se moque des constantes — les deux niveaux d'analyse coexistent, et le programme demande le premier.)

Deux mots sont anagrammes si et seulement si leurs dictionnaires de fréquences coïncident :

def sont_anagrammes(u: str, v: str) -> bool:
    return frequences(u) == frequences(v)      # exercice 3 ; comparaison de dicts

Pour grouper, il faut une clé canonique commune à tous les anagrammes d'un même groupe — le mot trié fait l'affaire :

def groupes_anagrammes(mots: list) -> list:
    groupes = {}
    for m in mots:
        cle = "".join(sorted(m))        # "chien" -> "cehin", "niche" -> "cehin"
        if cle not in groupes:
            groupes[cle] = []
        groupes[cle].append(m)
    return list(groupes.values())

g = groupes_anagrammes(["chien", "niche", "art", "rat", "tour"])
# [['chien', 'niche'], ['art', 'rat'], ['tour']]

sont_anagrammes est en $O(|u|+|v|)$ : deux comptages linéaires et une comparaison de dictionnaires (linéaire en leur taille). (L'idée de la clé canonique — représenter toute une classe d'équivalence par un représentant calculable — resservira sans cesse : c'est elle qui transforme « être équivalents » en « avoir la même clé », testable en $O(1)$ par dictionnaire.)

Si l'élément est en position $i$ (indices de $0$ à $n-1$), la boucle fait $i+1$ tours. La position étant uniforme :

$$\text{couˆt moyen}=\frac{1}{n}\sum _{i=0}^{n-1}(i+1)=\frac{1}{n}\cdot \frac{n(n+1)}{2}=\frac{n+1}{2}.$$

En moyenne, on lit donc la moitié du tableau — deux fois mieux que le pire cas $n$, mais toujours $O(n)$ : la classe asymptotique ne change pas. Le programme retient le pire cas pour trois raisons. D'abord, c'est une garantie : « au plus $n$ tours » est vrai pour toute entrée, quand la moyenne suppose un modèle probabiliste (ici l'uniformité — qui la justifie ?). Ensuite, les entrées réelles sont rarement uniformes : dans bien des applications, le cas défavorable est précisément le plus fréquent (chercher un mot absent d'un index, par exemple, coûte toujours le pire cas $n$). Enfin, le pire cas se calcule par un simple maximum, quand la moyenne exige de probabiliser l'espace des entrées — un outil que le cours de mathématiques ne fournira qu'en fin d'année. (L'analyse en moyenne n'est pas au programme, mais savoir qu'elle existe évite un contresens : « linéaire dans le cas le pire » ne signifie pas « toujours aussi lent ».)