Foros de matemática
28/07/2017, 10:01:21 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Renovado el procedimiento de inserción de archivos GEOGEBRA en los mensajes.
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Complejidad de una función: Algoritmos de ordenamiento.  (Leído 2070 veces)
0 Usuarios y 1 Visitante están viendo este tema.
dresuer
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 60


BOOOOOOM


Ver Perfil
« : 04/03/2017, 09:05:12 pm »

La parte de programación es bastante básica me parece más matemática que programación en sí,

Código:
for (int i= 0; i < N; i++) {
       for (int j= 0; j < i; j++) {
         algo_de_O(1)
       }
     }

En este caso, el apunte dice así:

el bucle exterior se realiza N veces, mientras que el interior se realiza 1, 2, 3, ... N veces respectivamente. En total,
1 + 2 + 3 + ... + N = N*(1+N)/2  -> O(n2)

Pero no entiendo por qué el (1+N)/2, ¿por qué N+1 y encima dividido 2?


Después tengo otra función:

Código:
void ssort (int data[], int sz){
  int i,j,min;
  for (i=0; i<sz; i++){
    min = i;
    for (j=i+1; j<sz; j++){
       if (data[i] < data[min])
          min = j;
     }
     swap(&data[i],&data[min]);
  }
}

Esta función lo que hace es ordenar un arreglo dado, en este caso, la complejidad de esta función es
N*(N-1)/2

Entiendo lo de N porque el bucle exterior se repite N veces pero, no entiendo el bucle interior.

Otras funciones como:

Código:
for (int i= 0; i < N; i++) {
       c= i;
       while (c > 0) {
         algo_de_O(1)
         c= c/2;
       }
     }
tenemos un bucle interno de orden O(log n) que se ejecuta N veces, luego el conjunto es de orden O(n log n)

Estas si las entiendo y tienen lógica para mi.


Espero alguna ayuda, saludos!
En línea
Juan Pablo
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 3.913


Ver Perfil
« Respuesta #1 : 04/03/2017, 09:13:46 pm »

Tienes que la sumatoria de los primeros [texx]n[/texx] naturales es [texx]\dfrac{n \cdot (n+1)} {2} [/texx]

Sea:

[texx] S_n = 1+ 2 + \cdots + (n-1) + n [/texx]

[texx] S_n = n+ (n-1) + \cdots + 2 + 1 [/texx]

Si sumamos las dos ecuaciones tenemos:

[texx] 2 \cdot S_n = (n+1) + (n+1) \cdots (n+1)  = n \cdot  (n+1) [/texx]
En línea
dresuer
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 60


BOOOOOOM


Ver Perfil
« Respuesta #2 : 04/03/2017, 09:42:39 pm »

Pero no entiendo o sea el primer bucle se repite 1+2+...+(n-1)+n veces y el interior se repite n+(n-1) + ... + 2+1  veces?

Yo no lo veo así, podrías explicar un poco más.
En línea
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 39.343


Ver Perfil
« Respuesta #3 : 05/03/2017, 06:54:35 am »

Hola

Pero no entiendo o sea el primer bucle se repite 1+2+...+(n-1)+n veces y el interior se repite n+(n-1) + ... + 2+1  veces?

Yo no lo veo así, podrías explicar un poco más.

Lo que tenemos que contar es cuantas veces se realiza la operación interna a ambos bucles (lo que llamas "algo de O(1)").

Entonces:

- Cuando [texx]i=0[/texx], el bucle interior no se realiza (la condición de fin de bucle se cumple desde el principio).
- Cuando [texx]i=1[/texx], el bucle interior realiza [texx]1[/texx] vez la operación, para [texx]j=0[/texx].
- Cuando [texx]i=2[/texx], el bucle interior realiza [texx]2[/texx] veces la operación, para [texx]j=0,1[/texx].
- Cuando [texx]i=3[/texx], el bucle interior realiza [texx]3[/texx] veces la operación, para [texx]j=0,1,2[/texx].

y así hasta:

- Cuando [texx]i=N-1[/texx], el bucle interior realiza [texx]N-1[/texx] veces la operación, para [texx]j=0,1,2,\ldots,N-1[/texx].

El número total de veces que se ha realizado la operación es:

[texx]0+1+2+3+\ldots+N-1[/texx]

¿Hasta aquí lo entiendes? En caso afirmativo lo que queda es saber o demostrar que esa suma equivale a [texx]\dfrac{N(N-1)}{2}[/texx]:

- Puedes verlo como la suma de los términos de una progresión aritmética de primer término [texx]0[/texx], úlimo [texx]N-1[/texx] y razón [texx]1[/texx].

- Puedes probarlo directamente como te ha indicado Juan Pablo (lo que ha hecho es la prueba de esa fórmula, para [texx]N[/texx] términos en lugar de para [texx]N-1[/texx]; pero la idea es la misma).

- Puedes probarlo por inducción.

 Entonces primero confirma que has entendido hasta la pregunta que he marcado en azul, en caso contrario pregunta que no entiendes del conteo de operaciones.

 Después si lo único que te queda por entender es esta igualdad:

[texx]0+1+2+3+\ldots+N-1=\dfrac{N(N-1)}{2}[/texx]

 indica si has intentado probarla por alguno de los tres caminos indicados y especifica la duda concreta que te surja.

Saludos.
En línea
dresuer
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 60


BOOOOOOM


Ver Perfil
« Respuesta #4 : 05/03/2017, 11:52:50 am »

Listo, ahora sí lo entendí.

Código:
void ssort (int data[], int sz){
  ALGO_DE_O(1)
  for (i=0; i<sz; i++){
    ALGO_DE_O(1)
    for (j=i+1; j<sz; j++){
       ALGO_DE_O(1)
     }
     ALGO_DE_O(1)
  }
}

Y en este caso empieza después, ¿cómo haría para contarlo? Yo si mal no recuerdo había leído en un apunte que en estos casos la mejor técnica es "emperar la función" o sea escribir algo como esto:

Código:
void ssort (int data[], int sz){
  ALGO_DE_O(1)
  for (i=0; i<sz; i++){
    ALGO_DE_O(1)
    for (j=0; j<sz; j++){
       ALGO_DE_O(1)
     }
     ALGO_DE_O(1)
  }
}

El bucle interno empieza directamente desde 0, entonces ahí sí es más facil calcular la complejidaqd, son dos bucles que se repiten n veces, por lo tanto la complejidad es O(n*n) = O(n^2)

Creo que era válido hacer esto, ¿o no?

Otra cosa, el profesor dijo que era innecesario que lo hagamos, de todos modos pregunto por si alguno sabe.

Analice la complejidad del algoritmo iterativo para calcular Fibonacci
Código:
int fibonacci(int n)
{
   if ( n == 0 )
      return 0;
   else if ( n == 1 )
      return 1;
   else
      return ( fibonacci(n-1) + fibonacci(n-2) );
}

¿Cuál sería la complejidad de esta función?

Saludos.
En línea
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 39.343


Ver Perfil
« Respuesta #5 : 06/03/2017, 07:44:26 am »

Hola

Listo, ahora sí lo entendí.

Código:
void ssort (int data[], int sz){
  ALGO_DE_O(1)
  for (i=0; i<sz; i++){
    ALGO_DE_O(1)
    for (j=i+1; j<sz; j++){
[color=red]       ALGO_DE_O(1)[/color]
     }
     ALGO_DE_O(1)
  }
}

Puedes hacer de manera análoga el razonamiento directo (para la operación central que marco en rojo):

Cuando [texx]i=0[/texx], [texx]j[/texx] varía desde [texx]1[/texx] hasta [texx]sz-1[/texx] ([texx]sz-1[/texx] operaciones).
Cuando [texx]i=1[/texx], [texx]j[/texx] varía desde [texx]2[/texx] hasta [texx]sz-1[/texx] ([texx]sz-2[/texx] operaciones).
...
Cuando [texx]i=sz-2[/texx], [texx]j[/texx] varía desde [texx]sz-1[/texx] hasta [texx]sz-1[/texx] ([texx]1[/texx] operaciónes).

En total:

[texx]1+2+\ldots+sz-1=\dfrac{sz(sz-1)}{2}[/texx]

Cita
Otra cosa, el profesor dijo que era innecesario que lo hagamos, de todos modos pregunto por si alguno sabe.

Analice la complejidad del algoritmo iterativo para calcular Fibonacci
Código:
int fibonacci(int n)
{
   if ( n == 0 )
      return 0;
   else if ( n == 1 )
      return 1;
   else
      return ( fibonacci(n-1) + fibonacci(n-2) );
}

¿Cuál sería la complejidad de esta función?

La complejidad se calcula igualmente recurivamente. Para los dos primeros términos se hace una operación:

[texx]T(0)=T(1)=1[/texx]

Después se tiene que:

[texx]T(n)=T(n-1)+T(n-2)+1[/texx] para [texx]n>2[/texx]

Ahora tienes que conocer las técnicas para resolver esa recurrencia.

Te quedará:

[texx]T(n)=(1-\dfrac{\sqrt{5}}{5})\left(\dfrac{1}{2}(1-\sqrt{5}\right)^n+(1+\dfrac{\sqrt{5}}{5})\left(\dfrac{1}{2}(1+\sqrt{5}\right)^n-1[/texx]

Asintóticamente:

[texx]
T(n)=O\left(\left(\dfrac{1}{2}(1+\sqrt{5}\right)^n\right)[/texx]

Saludos.
En línea
dresuer
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 60


BOOOOOOM


Ver Perfil
« Respuesta #6 : 07/03/2017, 01:14:16 am »

Buenísimo otra pregunta, que diferencia hay entre usar (Zeta) y la notación BIG O, me confundió un poco.

Yo siempre uso la notación Big O.





Si mi profesor en el examen de teoría me pide la definición de complejidad supongo que le voy a dar la de BIG O o no?, me confundí un poco.

Saludos.


* dreuser1.png (30.57 KB - descargado 214 veces.)
* dreuser2.png (26.34 KB - descargado 222 veces.)
En línea
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 39.343


Ver Perfil
« Respuesta #7 : 07/03/2017, 06:49:23 am »

Hola

Buenísimo otra pregunta, que diferencia hay entre usar (Zeta) y la notación BIG O, me confundió un poco.

Yo siempre uso la notación Big O.





La condición [texx]f\in \theta(g)[/texx] es más fuerte que [texx]f\in O(g)[/texx], es decir:

[texx] f\in \theta(g)\quad \Rightarrow{}\quad f\in O(g)[/texx]

La notación [texx]O(g)[/texx] en realidad sólo da una cota superior de la complejidad.

En cuanto a la definición de complejidad tu profesor debería de darte alguna concreta y tu aferrarte a ella; en principio la complejidad del algortimo es el tiempo que tarda en ejecutarse en función de su volumen de datos (si es un algoritmo que depende de [texx]n[/texx], pues el tiempo  en función de [texx]n[/texx]). Lo que ocurre que en la práctica no interesa tanto el tiempo exacto sino el "orden" de ese tiempo, es decir una cota asintótica de ese tiempo.

Saludos.


P.D. No pongas imágenes alojadas en servidores externos al foro. Debes primero de incluirlas en el mensaje como archivos adjuntos. Te lo he coregido yo esta vez.
En línea
dresuer
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 60


BOOOOOOM


Ver Perfil
« Respuesta #8 : 07/03/2017, 09:35:43 am »

Listo, una última pregunta más porque rindo el final teórico el jueves.

¿Sabés lo que es una hashtable?

Bueno tengo una duda en como crear una función hash que distribuya los elementos en las cubetas, vamos a suponer que tengo k cubetas y que quiero repartir los elementos en esa cantidad de cubetas.

La función hash trivial es esta.

Código:
void hashnat ( void *p, int cubetas ) {

  return *(int*)p % cubetas;
}

Eso devolvería un número entre 0 y el número máximo de las cubetas.

Ahora además de esa función trivial, ¿cuál sería otra función hash válida que reparta bien los elementos con la menor cantidad de colisiones posibles?
En línea
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 39.343


Ver Perfil
« Respuesta #9 : 07/03/2017, 01:54:21 pm »

Hola

¿Sabés lo que es una hashtable?

Bueno tengo una duda en como crear una función hash que distribuya los elementos en las cubetas, vamos a suponer que tengo k cubetas y que quiero repartir los elementos en esa cantidad de cubetas.

La función hash trivial es esta.

Código:
void hashnat ( void *p, int cubetas ) {

  return *(int*)p % cubetas;
}

Eso devolvería un número entre 0 y el número máximo de las cubetas.

Ahora además de esa función trivial, ¿cuál sería otra función hash válida que reparta bien los elementos con la menor cantidad de colisiones posibles?

 No sé mucho del tema y no acabo de entender exactamente que tiene que hacer esa función; exactamente cuál tiene que ser su entrada y cuál su salida.

Saludos.
En línea
dresuer
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 60


BOOOOOOM


Ver Perfil
« Respuesta #10 : 07/03/2017, 02:33:35 pm »

La función hash toma un natural y tiene que devolver un número entre un rango, o sea

Supongamos que tenemos R cubetas donde almacenaremos los valores.
Dado un espacio de claves (K), utilizamos una función para separar los valores. En general, esta función tiene la forma:

hash: K ->[0,R-1]

A un elemento con clave k, lo almacenaremos en la cubeta hash(k).

La función hash toma un natural en este caso y me tiene que dar un número entre 0 y el numero de cubetas que haya.

Supongamos que las cubetas son 10
La más común es el_numero % 10

Entonces ahi me devuelve un número entre 0 y por ejemplo 9, necesito hacer lo mismo pero con otra función.

En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.1 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!