Question

Nous avons une fonction qui prend un tableau en entrée. Il casse un tableau en $ log_2 (n) $ parties de tailles égales où $ n $ est la taille du sous-réseau. Il continue de briser chacun des sous-réseaux jusqu'à ce qu'il ne reste que deux éléments. Quelle est la profondeur de cette récursivité?

Exemple du processus:

Nous avons d'abord $ n $ éléments et les briser en $ log_2 (n) $ parties de tailles égales. Chacune de ces parties a $ frac {n} {log_2 (n)} $ éléments dedans. Dans le niveau suivant de la récursion, nous diviserons chacun des sous-réseaux en $ log_2 ( frac {n} {log_2 (n)}) $ parties à nouveau avec des tailles égales. Ceux-ci auront maintenant $ frac { frac {n} {log_2 (n)}} {log_2 ( frac {n} {log_2 (n)})} $ éléments dans chacun d'eux. Et nous continuons à briser le tableau de cette manière jusqu'à ce que nous atteignions un sous-réseau avec seulement deux éléments.

Pas de solution correcte

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top