Adloun

informatique (tronc commun des prépas scientifiques) · Chapitre 10 · Exercice de TD

L'espace caché de la récursivité

Prouver et analyser : la boîte à outils formalisée · niveau 2

Énoncé

Analyser la complexité temporelle et spatiale de la recherche dichotomique récursive dichotomie_rec(v, t, g, d).

Temps : $O (lo g n)$ . À chaque appel récursif, la taille de l'intervalle à traiter est divisée par 2.
Espace : $O (lo g n)$ . Bien qu'aucune structure de données auxiliaire ne soit allouée en cours d'exécution, la pile d'appels système doit stocker les contextes de chaque appel en attente. La profondeur maximale de récursion étant en $lo g_{2} (n) + 2$ , la complexité spatiale auxiliaire est logarithmique.