Calculateur de nœuds d'arbre de récursion

Les récurrences de type diviser pour régner de la forme T de n égale a fois T de n sur b plus le travail non récursif apparaissent dans tout cours d'algorithmes lorsque le tri fusion, les partitions spatiales binaires ou la récursion multiway sont dessinés en arbres. Les étudiants ont besoin d'un décompte fiable du nombre de nœuds à chaque niveau et de la profondeur atteinte avant que les sous-problèmes n'atteignent le cas de base. Ce calculateur de nœuds d'arbre de récursion accepte le facteur de branchement a, le rapport de réduction b et la taille d'entrée racine n, parcourt l'arbre jusqu'à ce que la taille du sous-problème soit au plus un, et renvoie le nombre de niveaux, la hauteur, les totaux de nœuds et de feuilles, la séquence de nœuds par niveau, les tailles de sous-problème et deux distributions fractionnaires du travail. L'une suppose un coût unitaire par nœud ; l'autre suppose un travail proportionnel à la taille du sous-problème, comme dans le schéma classique du tri fusion où chaque niveau complet effectue encore un travail linéaire en n.

Ce qu'un arbre de récursion compte et comment les niveaux sont définis

Un arbre de récursion est l'image de chaque sous-problème créé par un algorithme de type diviser pour régner dont le temps satisfait T de n égale a fois T de n sur b plus f de n. La racine représente l'instance d'origine de taille n. Chaque nœud interne a exactement a enfants, chacun résolvant un problème dont la taille est la taille du parent divisée par b.

Les niveaux sont numérotés à partir de zéro à la racine. Au niveau i il y a a puissance i nœuds, et chacun de ces nœuds a une taille de sous-problème n divisée par b puissance i, pourvu que les tailles restent réelles et positives. La marche continue tant que la taille courante est strictement supérieure à un ; le premier niveau dont la taille est inférieure ou égale à un est conservé comme niveau de feuilles des cas de base, puis la marche s'arrête.

Cette convention correspond à la condition d'arrêt des manuels pour résoudre directement les entrées de taille constante. La hauteur de l'arbre est le nombre de niveaux moins un, le nombre d'arêtes sur un chemin de la racine à une feuille. Les nœuds feuilles valent a élevé à la hauteur lorsque les tailles atteignent un sur une puissance exacte, et plus généralement le nombre de nœuds du dernier niveau enregistré.

Les nœuds internes sont le total moins les feuilles. Pour un facteur de branchement un, l'arbre est une seule épine de longueur égale au nombre de divisions successives jusqu'à ce que la taille soit au plus un. Pour un facteur supérieur à un, la forme fermée du total de nœuds sur L niveaux est a puissance L moins un, le tout sur a moins un ; ce point d'accès le recalcule en sommant la série géométrique afin que tailles fractionnaires et cas de base précoces restent cohérents avec la marche.

Quand compter les nœuds de l'arbre aide

Les cours d'algorithmes et les plateformes de tutorat utilisent un calculateur de nœuds d'arbre de récursion pour que les apprenants vérifient profondeur et largeur pour des a, b et n arbitraires sans dessiner des centaines de nœuds à la main. Les générateurs d'examens ont besoin d'un oracle déterministe qui marque comme fausse une prétendue comptée de feuilles ou de niveaux au lieu d'accepter des approximations asymptotiques vagues.

Les outils de préparation aux entretiens et les visualiseurs de complexité associent les tableaux par niveau à des graphiques pour que les candidats voient pourquoi un diviser pour régner équilibré dépense souvent le même travail à chaque niveau lorsque a égale b. Les carnets d'ingénierie qui prototypent des splitters multiway ou des graphes de tâches parallèles peuvent valider le fan-out avant d'écrire des ordonnanceurs de production. Une validation échouée ne consomme pas le solde.