Qu'est-ce qu'un algorithme ?

Question

Accepted Answer

Un **algorithme** est une séquence finie et bien définie d'étapes qui transforme une entrée en la sortie souhaitée. Nous l'évaluons selon deux axes : la **correction** (produit-il toujours la bonne réponse ?) et l'**efficacité** (combien de temps et de mémoire utilise-t-il ?).

## Pourquoi c'est important

Un algorithme valide doit être *sans ambiguïté* (chaque étape est claire), *fini* (il se termine), et produire le résultat *correct* pour chaque entrée valide.

## Exemple

```python
# Find the maximum value in a list
def find_max(nums):
    if not nums:
        return None          # handle empty input
    largest = nums[0]        # assume first is the max
    for n in nums[1:]:       # scan the rest
        if n > largest:
            largest = n      # update when we see something bigger
    return largest

find_max([3, 9, 2, 7])       # -> 9
```

Ceci visite chaque élément une seule fois.

## Complexité

- **Temps :** O(n) — un passage sur n éléments.
- **Espace :** O(1) — juste une variable supplémentaire.

## Quand c'est important / pièges

Même problème, de nombreux algorithmes avec des coûts différents. Vérifiez toujours les cas limites (entrée vide, élément unique, doublons) — c'est là que la correction échoue généralement.

## Pourquoi c'est important

Les algorithmes sont au cœur de la résolution de problèmes en informatique.

Deux programmes peuvent produire la même réponse tandis que l'un est des milliers de fois plus rapide.

Penser en termes de correction *et* d'efficacité est ce qui distingue le code qui fonctionne sur un cas de test du code qui fonctionne à grande échelle.

C'est aussi le langage commun des entretiens techniques et des discussions de conception de systèmes.