[dresuer]

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

Código: [Seleccionar]

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: [Seleccionar]

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: [Seleccionar]

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!

[Juan Pablo Sancho]

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

Sea:

\(  S_n = 1+ 2 + \cdots + (n-1) + n  \)

\(  S_n = n+ (n-1) + \cdots + 2 + 1  \)

Si sumamos las dos ecuaciones tenemos:

\(  2 \cdot S_n = (n+1) + (n+1) \cdots (n+1)  = n \cdot  (n+1)  \)

[dresuer]

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.

[Luis Fuentes]

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 \( i=0 \), el bucle interior no se realiza (la condición de fin de bucle se cumple desde el principio).
- Cuando \( i=1 \), el bucle interior realiza \( 1 \) vez la operación, para \( j=0 \).
- Cuando \( i=2 \), el bucle interior realiza \( 2 \) veces la operación, para \( j=0,1 \).
- Cuando \( i=3 \), el bucle interior realiza \( 3 \) veces la operación, para \( j=0,1,2 \).

y así hasta:

- Cuando \( i=N-1 \), el bucle interior realiza \( N-1 \) veces la operación, para \( j=0,1,2,\ldots,N-1 \).

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

\( 0+1+2+3+\ldots+N-1 \)

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

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

- Puedes probarlo directamente como te ha indicado Juan Pablo (lo que ha hecho es la prueba de esa fórmula, para \( N \) términos en lugar de para \( N-1 \); 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:

\( 0+1+2+3+\ldots+N-1=\dfrac{N(N-1)}{2} \)

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

Saludos.

[dresuer]

Listo, ahora sí lo entendí.

Código: [Seleccionar]

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: [Seleccionar]

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: [Seleccionar]

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.

[Luis Fuentes]

Hola

Listo, ahora sí lo entendí.

Código: [Seleccionar]

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 \( i=0 \), \( j \) varía desde \( 1 \) hasta \( sz-1 \) (\( sz-1 \) operaciones).
Cuando \( i=1 \), \( j \) varía desde \( 2 \) hasta \( sz-1 \) (\( sz-2 \) operaciones).
...
Cuando \( i=sz-2 \), \( j \) varía desde \( sz-1 \) hasta \( sz-1 \) (\( 1 \) operaciónes).

En total:

\( 1+2+\ldots+sz-1=\dfrac{sz(sz-1)}{2} \)

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: [Seleccionar]

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:

\( T(0)=T(1)=1 \)

Después se tiene que:

\( T(n)=T(n-1)+T(n-2)+1 \) para \( n>2 \)

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

Te quedará:

\( 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 \)

Asintóticamente:

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

Saludos.

[dresuer]

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.

[Luis Fuentes]

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 \( f\in \theta(g) \) es más fuerte que \( f\in O(g) \), es decir:

\(  f\in \theta(g)\quad \Rightarrow{}\quad f\in O(g) \)

La notación \( O(g) \) 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 \( n \), pues el tiempo  en función de \( n \)). 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.

[dresuer]

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: [Seleccionar]

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?

[Luis Fuentes]

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: [Seleccionar]

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.