Complexité du calcul

10

Quelle est la complexité du calcul ?nn2,nN

Raphael
la source
2
Qu'as- tu essayé? Quelle machine et quel modèle de coûts supposez-vous?
Raphael

Réponses:

12

En utilisant la transformée de Fourier rapide, les multiplications sur les nombres à bits peuvent être effectuées dans le temps (où le tilde signifie que nous ignorons les facteurs polylogarithmiques). Par la mise au carré répétée, nous pouvons calculer avec multiplications, et chaque multiplication n'implique aucun nombre supérieur à , qui a environ bits. Ainsi, le temps total requis est .kO~(k)nn2O(logn)nn2n2log2nO~(n2(logn)2)=O~(n2)

Michée
la source
3

Modifié en réponse aux commentaires Le temps de calcul peut être décomposé en le temps requis pour calculer et celui requis pour effectuer . Je suppose que la multiplication d'un nombre bits par un nombre bits prend exactement temps par la méthode du livre scolaire; les ajouts, etc. sont à temps constant. Par conséquent, le calcul de prend du temps .f(n)=nn2f1(n)=n2nf1(n)mnmnn2log22(n)

Supposons que nous utilisons l'exponentiation binaire pour calculer . L'exponentiation binaire effectue deux types d'opérations dans le calcul de : la mise au carré du produit actuel et la multiplication du produit actuel par , selon que le bit actuel dans l'expansion binaire de est 0 ou 1. Dans le pire des cas , est une puissance de deux, de sorte que l'exponentiation binaire place à plusieurs reprises son produit actuel jusqu'à ce qu'il atteigne la réponse.Notez que a bits, de sorte que le nombre de ces équerrages est . C'est le cas que nous analysons plus loin.f(n)f(n)nn2n2n2m=2log2(n)m=m1

Le premier quadrillage prend temps, résultant en un produit bits. La seconde mise au carré prend deux bits et s'exécute en fois, résultant en un produit bits. En continuant, la ème étape prend fois et un produit bits. Ce processus s'arrête à la -ième étape; en conséquence, cela prend du tempst1=log22(n)o1=2log2(n)o1t2=o12o2=2o1iti=4i1log22noi=2ilog2(n)m

Texp=[1..m]ti=log22(n)[1..m]4i=4m13log22n .

Lorsque le coût de mise au carré initial est inclus, nous constatons que nous avons besoin de temps au maximum

Texp+log22n

Remarque

  • J'ai omis certains planchers et plafonds dans les calculs, en espérant qu'ils n'affecteraient pas matériellement la réponse.
  • J'ai délibérément omis une analyse basée sur en faveur d'une limite supérieure exacte juste pour être rigoureuse. O
  • Le raisonnement ci-dessus montre également pourquoi mon analyse antérieure était erronée. La notation été utilisée de manière rapide et lâche, et elle a commodément omis des constantes de sorte que, par exemple, est devenu par magie . OtiO(logn)
  • Les multiplications peuvent toujours être accélérées par la FFT et d'autres méthodes.
PKG
la source
1
Comment avez-vous obtenu la complexité de pour le calcul de ? O(1)n2
4
Je vais vous dire que la multiplication de deux nombres à bits prend du temps au lieu du temps , vous devez également comprendre cela dans le coût de l'exponentiation binaire. nO(logn)O(1)
Mark Dominus
2
Notez que le résultat final a bits. Il est très difficile de calculer bits en temps . n2log2nn2log2nO(logn)
Bon point, je vais prendre note
PKG
1
@ThomasAndrews: Cela dépend de la machine et du modèle de coût. Il n'est pas rare de supposer un modèle RAM avec un coût constant pour les ajouts.
Raphael