[mg]

Hola,

Estoy intentando hacer el ejercicio del título. La respuesta ha de ser \( log^2 n \) donde \( n\in{\mathbb{Z}_+} \).

Para ello yo he escrito un algoritmo, que no es mas que el habitual

\( c \;vector\;\;\;\;, k=0\;\;\;\;\;\;\;\;\;
while \;n\; distinto \;de \;1,0
\left\{{k=k+1\;\;\;\;\;\;\;\;
mod n/2=c[k]\;\;\;\;\;\;\;\;\;\;
n=n/2\;\;\;\;\;\;\;\;\;\;\;
}\right\}\;\;\;\;\;\;
c[k+1]=n \)

C es el vector que va a dar como resultado el número en binario. Sabemos que el while va a repetirse a sumo \( \left<{log_2n}\right> \) (parte entera del log). El problema es calcular la complejidad de \( mod n/2 \), que es tomar el resto de la división \( n/2 \). No sé si esta complejidad sería la misma que dividir \( n/2 \). A lo mejor es \( o(dividir)+o(restar) \), por el teorema de la división entera.

Además, he demostrado que la complejidad de multiplicar dos números binarios de \( k \) y \( l \) cifras es \( o(k) \) si k es mayor que l. Pero no sé la complejidad de dividir. ¿Es la misma que multiplicar?

Un saludo.

[martiniano]

Hola.

Hola,

Estoy intentando hacer el ejercicio del título. La respuesta ha de ser \( log^2 n \) donde \( n\in{\mathbb{Z}_+} \).

Para ello yo he escrito un algoritmo, que no es mas que el habitual

\( c \;vector\;\;\;\;, k=0\;\;\;\;\;\;\;\;\;
while \;n\; distinto \;de \;1,0
\left\{{k=k+1\;\;\;\;\;\;\;\;
mod n/2=c[k]\;\;\;\;\;\;\;\;\;\;
n=n/2\;\;\;\;\;\;\;\;\;\;\;
}\right\}\;\;\;\;\;\;
c[k+1]=n \)

C es el vector que va a dar como resultado el número en binario. Sabemos que el while va a repetirse a sumo \( \left<{log_2n}\right> \) (parte entera del log). El problema es calcular la complejidad de \( mod n/2 \), que es tomar el resto de la división \( n/2 \). No sé si esta complejidad sería la misma que dividir \( n/2 \).

En cualquier caso no va a ser mayor, y como en una de las sentencias del bloque de instrucciones del bucle divides \[ n \] entre dos, pues esa va a ser la complejidad del bloque de instrucciones del bucle.

Yo diría que la complejidad de dividir \[ n \] entre dos es del orden del número de cifras de \[ n \], que también es \[ O(\log_2n) \], con lo que el coste total a mí me sale \[ O(\log_21+\log_22+...+\log_2n)=O(n\log_2n) \], si no me equivoco.. .

Un saludo.

[Masacroso]

Es que la complejidad depende del algoritmo que uses, ¿cómo se demuestra que existe un algoritmo óptimo? ¿Se puede hacer eso? Quizá en algunos casos sí pero, por ejemplo, para multiplicar dos números, a día de hoy, se siguen sacando algoritmos nuevos cada vez más óptimos que los anteriores (al menos comentaban eso en este vídeo).

[mg]

Hola.

Hola,

Estoy intentando hacer el ejercicio del título. La respuesta ha de ser \( log^2 n \) donde \( n\in{\mathbb{Z}_+} \).

Para ello yo he escrito un algoritmo, que no es mas que el habitual

\( c \;vector\;\;\;\;, k=0\;\;\;\;\;\;\;\;\;
while \;n\; distinto \;de \;1,0
\left\{{k=k+1\;\;\;\;\;\;\;\;
mod n/2=c[k]\;\;\;\;\;\;\;\;\;\;
n=n/2\;\;\;\;\;\;\;\;\;\;\;
}\right\}\;\;\;\;\;\;
c[k+1]=n \)

C es el vector que va a dar como resultado el número en binario. Sabemos que el while va a repetirse a sumo \( \left<{log_2n}\right> \) (parte entera del log). El problema es calcular la complejidad de \( mod n/2 \), que es tomar el resto de la división \( n/2 \). No sé si esta complejidad sería la misma que dividir \( n/2 \).

En cualquier caso no va a ser mayor, y como en una de las sentencias del bloque de instrucciones del bucle divides \[ n \] entre dos, pues esa va a ser la complejidad del bloque de instrucciones del bucle.

Yo diría que la complejidad de dividir \[ n \] entre dos es del orden del número de cifras de \[ n \], que también es \[ O(\log_2n) \], con lo que el coste total a mí me sale \[ O(\log_21+\log_22+...+\log_2n)=O(n\log_2n) \], si no me equivoco.. .

Un saludo.

Pues teniendo eso en cuenta mañana lo revisaré y veo si tengo el mismo resultado.

Es que la complejidad depende del algoritmo que uses, ¿cómo se demuestra que existe un algoritmo óptimo? ¿Se puede hacer eso? Quizá en algunos casos sí pero, por ejemplo, para multiplicar dos números, a día de hoy, se siguen sacando algoritmos nuevos cada vez más óptimos que los anteriores (al menos comentaban eso en este vídeo).

Claro, por eso tiene importancia el estudio de la complejidad. De hecho, como la respuesta al ejercicio es \( o(log^2n) \) te reto a que encuentres el algoritmo que da tal complejidad  (no hay por qué aceptarlo).

Un saludo y gracias a ambos.


PD: Añado que en este contexto la base del logaritmo es 2.

[martiniano]

Hola.

¿Has visto recursividad de tipo "divide y vencerás"? No lo he analizado a fondo pero creo que el siguiente algoritmo podría funcionar.

Dado un natural \[ n \] busca el menor natural \[ k \] tal que \[ 2^{2k}>{n} \].

Expresa \[ n \] en base \[ 2^k \], esto es, halla \[ a, b<2^k \] tales que \[ a\cdot{2^k+b}=n \].

Llama recursivamente al algoritmo para obtener las representaciones binarias de \[ a \] y \[ b \] y concaténalas.

Como casos triviales basta que des las representaciones de \[ 1 \] y \[ 0 \].

Un saludo.

[mg]

Yo diría que la complejidad de dividir \[ n \] entre dos es del orden del número de cifras de \[ n \], que también es \[ O(\log_2n) \], con lo que el coste tal a mí me sale \[ O(\log_21+\log_22+...+\log_2n)=O(n\log_2n) \], si no me equivoco.. .

Coincido con tus cálculos

Hola.

¿Has visto recursividad de tipo "divide y vencerás"? No lo he analizado a fondo pero creo que el siguiente algoritmo podría funcionar.

Dado un natural \[ n \] busca el menor natural \[ k \] tal que \[ 2^{2k}>{n} \].

Expresa \[ n \] en base \[ 2^k \], esto es, halla \[ a, b<2^k \] tales que \[ a\cdot{2^k+b}=n \].

Llama recursivamente al algoritmo para obtener las representaciones binarias de \[ a \] y \[ b \] y concaténalas.

Como casos triviales basta que des las representaciones de \[ 1 \] y \[ 0 \].

Un saludo.

Creo que al principio quieres decir \( 2^k \).

Creo que podría funcionar, aunque claro habría que hallar el coste de la exponenciación.

Para ello se me ocurre suponer que k es impar, pues sería lo que mayor coste tendría entonces tenemos que \( k=2m+1 \) con m natural. Por tanto para hacer la exponenciación vamos a hacer primero \( 2^2 \) exactamente \( m/2 \) veces. entonces ahora si \( m/2 \) es distinto de 1 seguimos haciendo esto recursivamente, de modo que el coste de multiplicarlo se va a reducir. En gordo haríamos este proceso \( log 2m \) veces a lo que habría que sumarle la última multiplicación porque \( k=2m+1 \). Por tanto sería \( o(1+2+...+log 2m+log 2m)=o(nlog 2m)=o(log m) \)

Ahora no tengo más tiempo pero tiene pinta de dar lo que se espera.

[martiniano]

Hola.

Creo que al principio quieres decir \( 2^k \).

No. Quería poner \[ 2^{2k} \]. La idea es hallar una potencia de 2 tal que la representación de \[ n \] en esa base tenga exactamente dos cifras y así poder realizar llamadas recursivas con cada una de esas cifras.

El hecho de que la base sea una potencia de 2 garantiza que al concatenar las representaciones en base 2 de \[ a \] y de \[ b \] tengamos la de\[ n \].

Por ejemplo imagínate que queremos codificar en binario \[ 172 \]. Tenemos que \[ 2^{2\cdot{4}}=256>172 \]. Buscamos el cociente y el resto de dividir \[ 172 \] entre \[ 2^4=16 \] y nos queda que \[ 172=10\cdot{16+12} \]. Ahora haríamos la llamada recursiva y nos queda que \[ 10=1010_{2)} \] y \[ 12=1100_{2)} \] con lo que \[ 172=10101100_{2)} \]

Igual hay que perfilar algún detalle para que acabe entrando en la complejidad que dices, pero tengo la sensación de que debemos de estar cerca. Tal vez el cálculo de \[ k \] hay que dejarlo fuera del algoritmo recursivo. A ver si mañana saco algo de tiempo para mirarlo tranquilamente. Hoy me ha resultado imposible.

Un saludo.

[martiniano]

Hola.

Hola.

Creo que al principio quieres decir \( 2^k \).

No. Quería poner \[ 2^{2k} \]. La idea es hallar una potencia de 2 tal que la representación de \[ n \] en esa base tenga exactamente dos cifras y así poder realizar llamadas recursivas con cada una de esas cifras.

Al final ha resultado ser \[ 2^{2^k} \]. He implementado el algoritmo en Java y he hecho algunas pruebas. Parece que funciona bien.

Código: [Seleccionar]

package enbase2;
import java.util.ArrayList;
public class EnBase2 {
    private static ArrayList arrayDosALaK;
    private static ArrayList arrayDosALaDosALaK;
   
    /*Devuelve un array con la representación binaria de n.
    El número de dígitos es 2^(k+1) tal que 2^(2^k)>=n salvo para el cero y el
    uno que devuelve un solo dígito*/
    public static int[] toBase2(int n){
        if (n==1||n==0){
            int [] codN=new int [1];
            return codN;
        }
        int k=0;
        int dosALaK=1;
        int dosALaDosALaK=2;
        arrayDosALaK=new ArrayList();
        arrayDosALaDosALaK=new ArrayList();
        arrayDosALaK.add(dosALaK);
        arrayDosALaDosALaK.add(dosALaDosALaK);
        while(dosALaDosALaK*dosALaDosALaK<=n){
            dosALaDosALaK=dosALaDosALaK*dosALaDosALaK;
            dosALaK=2*dosALaK;
            k++;
            arrayDosALaK.add(dosALaK);
            arrayDosALaDosALaK.add(dosALaDosALaK);
        }
        return toBase2(n,k);
    }
   
    /*Devuelve la representación binaria de n con 2^(k+1) dígitos*/
    public static int[] toBase2(int n, int k){
        if (k==-1){
            int [] codN=new int [1];
            codN[0]=n;
            return codN;
        }
        int numDigitos=(int)arrayDosALaK.get(k);
        int[] codN=new int [2*numDigitos];
        if (n==1||n==0){
            codN[2*numDigitos-1]=n;
            for (int i=0;i<2*numDigitos-1;i++){
                codN[i]=0;
            }
            return codN;
        }
        int base =(int)arrayDosALaDosALaK.get(k);
        int a=n/base;
        int b=n%base;
        int[] codA=toBase2(a,k-1);
        int[] codB=toBase2(b, k-1);
        int i;
        for ( i=0;i<numDigitos;i++){
            codN[i]=codA[i];
        }
        for ( i=0;i<numDigitos;i++){
            codN[i+numDigitos]=codB[i];
        }
        return codN;
    }
   
    /*Main para hacer pruebas*/
    public static void main(String[] args) {
        for (int j=0;j<35124;j++){
            int [] array=toBase2(j);
            System.out.print(j+":\t");
            for (int i=0;i<array.length;i++){
                System.out.print(array[i]);
            }
            System.out.println();
        }
    }
}

También parece que lo más costoso es calcular todas las potencias de la forma \[ 2^k \] y \[ 2^{2^k} \] tales que \[ 2^{2^k}\leq{n} \]. Si no me equivoco eso se hace en \[ O((\log(\log(n)))^2)  \].

Un saludo.