Big O complexité des opérations arithmétiques de base

Question

Quelle est la complexité Big-O pour les algorithmes répandus des opérations arithmétiques de base comme la multiplication, la racine carrée, le logarithme, le scalaire et le produit matriciel? Y at-il des algorithmes exotiques qui sont plus efficaces, en termes de complexité Big-O, mais qui ne sont pas très répandus dans les solutions pratiques (par exemple, non implémentés dans les bibliothèques de logiciels populaires)?

Answer 1

Voir http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

---

produit de matrices des matrices carrées:

• O (N) (méthode naïve)
• O (N ^2,81) (Strassen's algorithm).

Il y a aussi un O (N ^2,38) Coppersmith–Winograd algorithm mais je ne pense pas qu'il est répandue en raison de l'énorme constante caché.

multiplication Big-int:

• Naïf: O (n)
• rapide transformée de Fourier base: O (n log n log log n) (Schönhage–Strassen algorithm).

Il existe également un n log n & middot; 2 ^{O (log * n)} algorithme publié en 2008 mais qui était trop nouveau pour être répandu.

---

Habituellement, la méthode naïve est assez bonne pour une entrée de taille normale.

Answer 2

Les opérations n'ont pas de complexité, contrairement aux algorithmes. Par exemple, il existe différents algorithmes de racine carrée, et ils auront une complexité différente.

Answer 3

Vous considérerez la plupart des opérations simples comme O (1) car votre taille d'entrée est généralement fixe (c'est-à-dire 32 ou 64 bits). Dans des conditions normales, votre plate-forme effectuera exactement la même opération pour la multiplication, la racine carrée, le logarithme, etc., quelle que soit la "taille" de votre entrée (par exemple int a = 0 et int b = Int32.MaxValue sont les deux entiers 32 bits).

Cela devient intéressant quand vous commencez à regarder des matrices ou à représenter des nombres de précision arbitraire, mais quelqu'un a déjà lié le résumé de wikipedia, donc je ne vais pas entrer dans ça. N'utilisez pas Schönhage–Strassen pour multiplier les petits nombres "normaux". Ça va me faire pleurer. Juste parce qu'un algorithme est O (n ) ne signifie pas qu'il est mauvais - surtout quand n est presque toujours 2 ou 2 .

Answer 4

La racine carrée et le logarithme peuvent être implémentés de diverses manières, affectant grandement la complexité (jugée par la précision requise). Si elles sont implémentées avec des tables de recherche (et une sorte d'interpolation), l'exigence de mémoire explose vraiment car plus de précision est requise mais la complexité est de rechercher la valeur dans le tableau et éventuellement d'appliquer l'interpolation.

Plus généralement, ils semblent être implémentés par leurs définitions de séries. Recurve ou itère une déclaration pour un certain nombre de tours jusqu'à ce que vous atteigniez la précision requise. Ici le nombre de tours peut devenir très élevé car plus de précision est nécessaire, et les calculs eux-mêmes sont affectés par la précision accrue.

Answer 5

Il y a un algorithme de type Fourier qui fait la multiplication entier ainsi (Schonhage-Strassen)

Je pensais qu'il y avait une version de l'algorithme de Strassen qui fait un peu mieux que la normale pour la multiplication entier, mais maintenant que je pense, celui-là finit par être le même que simple ...

L'addition et la soustraction sont à peu près, juste l'addition et la soustraction. Division et la racine carrée sont probablement intéressants si ...

AUSSI: Notez que jusqu'à présent, tout le monde a parlé de l'arithmétique INTEGER. Une fois que vous arrivez à flotteurs/doubles tous les paris sont désactivés. Ensuite, vous entrez dans le monde de numerical analysis, et c'est tout un champ de son propre ...

Answer 6

Jetez un oeil à BigInteger, sur des entiers de longueur arbitraire. Tout a maintenant un coût, en termes de taille de l'entrée, qui est le nombre de bits (généralement O(log K) bits pour un nombre K). Je vais utiliser N pour le nombre de bits ci-dessous. Par exemple, l'addition et la soustraction sont maintenant O(N). La multiplication est O(N^2) (naïf) ou O(n (log n)^(2+epsilon) ) avec FFT.

D'autres algorithmes incluent la fonction "power", qui prend la multiplication O(N). (excepté maintenant chaque multiplication a un coût!)

Et il y a des complexités supplémentaires pour BigDecimals, qui est l'équivalent décimal de longueur arbitraire, et au-delà de certaines opérations plus basiques, certaines des choses sont plus intéressantes aussi (surtout si vous voulez comprendre combien de précision vous voulez). Vous pouvez jeter un oeil à l'implémentation de Java.

Answer 7

La division et les racines carrées pour un grand nombre de bits ne sont pas beaucoup plus complexes que la multiplication. Pour les deux opérations, l'ancienne itération de Newton peut être arrangée de telle sorte que l'itération de Newton n'ait que des multiplications. Puisque le nombre de chiffres corrects est doublé à chaque étape, nous pouvons simplement doubler la précision du calcul à chaque étape.