En Wikipedia ( aquí ), dice que la multiplicación larga de un libro escolar $n$ -El número de un dígito tiene complejidad $O(n^2)$ . ¿Puede alguien ayudar a proporcionar una referencia para esta afirmación?
Además, ¿depende esta reivindicación de la base en la que el número $n$ se expresa, o es la misma para todas las bases?
Si quieres una referencia, se trata al principio del primer capítulo de Algoritmos por Dasgupta, Papadimitriou y Vazirani (Recuerdo vagamente otro libro de texto que también comienza con un tratamiento de la aritmética de los números naturales, pero no lo encuentro, y es posible que esté pensando en el libro que mencioné antes).
Si $a$ y $b$ son $n$ -números de un dígito, entonces cuando multiplicamos $a$ y $b$ utilizando el método del libro escolar, multiplicamos cada dígito de $b$ con cada dígito de $a$ , dándonos $n^2$ multiplicaciones de un solo dígito. A continuación, realizamos $(n-1)$ sumas de números, cada uno con un máximo de $2n$ dígitos. Como cada suma es $O(2n) = O(n)$ la parte de adición del proceso también es $O(n^2)$ .
La afirmación es cierta independientemente de la base en la que estén escritos los números. Tenga en cuenta que $n$ representa el número de dígitos del número en la base en la que están escritos, pero en realidad la afirmación es cierta incluso si $n$ es el número de dígitos de base-10, y el cálculo se realiza en alguna otra base.
Para ver esto, observe que el número de dígitos de base 10 de un número natural $m$ es $$ \left\lfloor \log_{10} (m) \right\rfloor + 1 $$ mientras que el número de base $b$ dígitos de $m$ es $$ \left\lfloor \log_b (m) \right\rfloor + 1. $$
Desde $$ \log_b (m) = \frac{\log_{10} (m)}{\log_{10} (b)}, $$ vemos que el número de base- $b$ dígitos de $m$ es como máximo un factor constante del número de dígitos de base-10.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
1 votos
Hay algunos conceptos erróneos. Según la definición de algoritmo de libro escolar, la complejidad para multiplicar dos números de n cifras es $O(n^2)$ . Si se multiplica por un número de 1 cifra es $O(n)$ si se multiplica por un número de m cifras es $O(nm)$ todo ello medido en multiplicaciones de un solo dígito. La base de $n$ es irrelevante, es sólo un número. Si representas los números en otra base, las multiplicaciones de un dígito son en esa base.
0 votos
Para una referencia, véase, por ejemplo, Algorithm 1.2. en R.P. Brent, P. Zimmermann: Modern Computer Arithmetic, Cambridge University Press, 2011. Una versión preliminar del libro está disponible en maths.anu.edu.au/~brent/pd/mca-cup-0.5.9.pdf
0 votos
Suponiendo que la multiplicación y suma de literales enteros de un solo dígito sea $O(1)$ para la multiplicación de a $m$ -con una $n$ número de -dígitos donde $m\leq n$ necesitamos como máximo $mn+k+a$ pasos donde $k$ denota el número de transportes y $a$ es el número de pasos para añadir el $m$ -valores para obtener el resultado final. Es evidente que $k,a\leq mn$ por lo que la complejidad temporal es $O(mn)$