Traiter de très grands nombres avec la programmation Python

Question

Lorsque nous parlons de la complexité de nos codes la plupart du temps, nous considérons le nombre d'entrées. Habituellement, nous ne considérons pas beaucoup à propos de la mise en œuvre du matériel de pose. Pour obtenir une connectivité entre la complexité du code et le nombre d'entrées que nous composons à notre algorithme (Code) nous utilisons couramment la notation Big_O. La boucle est la chose essentielle pour implémenter l'algorithme mais elle a la complexité de O (n) qui signifie que le temps grandira linéairement avec le nombre d'entrée si grand nombre d'entrées il inefficace. mais nous pouvons remplacer la boucle par la récursion car la récursion a toujours la complexité du temps O (log n). Et je ne vais pas le clarifier ici. De tout cela ci-dessus Mais je veux dire que la récursivité est plus efficace que la boucle

et aussi tout ce qui peut faire une boucle, nous pouvons faire la même chose par la récursivité plus efficacement.

donc je trouve une question de Project Euler.net appel self powers

suite est ma question

La série, 11 + 22 + 33 + ... + 1010 = 10405071317. Trouver les dix derniers chiffres de la série, 11 + 22 + 33 + ... + 10001000.

cette question semble facile si je mets en œuvre mon code de Python et son travail en douceur pour petit nombre de nombre de gammes mais obtenir une puissance de 1000 à 1000 et la somme de tous les python ci-dessus montrent généralement une erreur (parce que les nombres sont extrêmement élevés, ce qui est suffisant pour le flux de la mémoire en python). suivi est mon code

def f(n): 
    if n==1: 
     return 1 
    else: 
     return n**n+f(n-1) 

Alors ma question est comment puis-je résoudre ce problème, et comment je traiter ces très grand nombre, comment puis-je gérer les exceptions qui aura lieu sur un grand nombre d'entiers s'il vous plaît mentionner bon algorithme motivatif?

Answer 1

Rien ne rend la récursion intrinsèquement plus efficace. De plus, le même algorithme implémenté avec la récursivité est susceptible d'être moins efficace en raison de l'en-tête d'appel de fonction. Pire que cela, et c'est exactement votre cas, l'utilisation de récursions de grande profondeur est susceptible de provoquer un débordement de pile (sans jeu de mots). A moins que l'optimisation de tail-recursion soit utilisée, ce qui n'est pas en Python.

Python n'a aucune limite (dans des limites raisonnables) de taille de nombre entier, et ce n'est pas le problème. Re-implémenter la fonction en utilisant une boucle, et vous ferez bien. Sauf que n ** n ne fait pas ce que vous semblez penser.