16/09/2019, 11:22:41 pm *
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: ¡Atención! Hay que poner la matemática con LaTeX, y se hace así (clic aquí):
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Análisis de un algoritmo  (Leído 1680 veces)
0 Usuarios y 1 Visitante están viendo este tema.
pierrot
pabloN
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 3.348


Ver Perfil
« : 28/08/2012, 12:16:43 am »

Dado el siguiente algoritmo que recibe como parámetro un arreglo a de tamaño n de enteros distintos, interesa calcular el costo en el mejor ([texx]T_B(n)[/texx]) y peor ([texx]T_W(n)[/texx]) caso, considerando simultáneamente las dos siguientes operaciones elementales:

-La comparación entre elementos de a con costo c1.
-La asignación en el arrego a con costo c2.

Se pide:

1) Indique en forma genérica las entradas de tamaño n que maximizan el costo y luego calcule el costo del peor caso.

2) Indique en forma genérica las entradas de tamaño n que minimizan el costo y luego calcule el costo del mejor caso.


for(int=1; i<n-2; i=i+4){
   if (a[i] > a[i+2])
      swap(a, i-1, i+1);
}

for(int=0; i<n; i=i++){
   for(j=i+1; j<=n; i++)
      if (a[i] > a[j])
         swap(a, i, j);
}

void swap (int* a; int i; int j){
   int aux=a[i];
   a[i]=a[j];
   a[j]=aux;
}


Para el apartado 2) es claro que el mejor caso se da cuando el arreglo está ordenado. Pero para el apartado 1), ¿cuándo se da el peor caso? ¿Será cuando el arreglo está ordenado en sentido inverso? No lo veo tan claro.
En línea

$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print
Phicar
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Colombia Colombia

Mensajes: 514



Ver Perfil WWW
« Respuesta #1 : 28/08/2012, 01:04:38 am »

Hola pabloN, sí el peor caso es el que estén al revés..nota que se necesitan [texx]n^2-\displaystyle\binom{n}{2}[/texx] o [texx]O(n^2)[/texx]



Ahora, para tu problema, pues usa el arreglo para hacer la inversa...digamos el arreglo más complicado(longitud 10) para el bubble sort sería 10 9 8 7 6 5 4 3 2 1 pero el for de antes lo volverá así

8 9 10 7 4 5 6 3 2 1 luego si lo metes de ésta forma, te quedará ordenado al revés. Así que al algoritmo le tomará [texx]10^2-\displaystyle\binom{10}{2}+2[/texx] swaps.

para curarme en dudas hice un bruteforce..

Cita
import java.util.*;
public class pablo{
public static int max = -1;
public static void main(String args[]){
gen(10,new Vector<Integer>(),10);
System.out.println(max);
}
public static int buble(Vector<Integer> aa){
int a[] = new int[aa.size()];
for(int n = 0;n<aa.size();n++)
a[n]=aa.get(n);
int res = 0;
for(int i=1; i<aa.size()-2; i=i+4){
if (a > a[i+2]){
res++;
a[i-1]^=a[i+1];
a[i+1]^=a[i-1];
a[i-1]^=a[i+1];
}
}
for(int i=0; i<aa.size();i++){
for(int j=i+1; j<aa.size(); j++)
if (a > a[j]){
res++;
a^=a[j];
a[j]^=a;
a^=a[j];
}
}
return res;
}
public static void gen(int a,Vector<Integer> b,int c){
if(a==0){
int bu = buble(b);
if(bu>max){
max = bu;
System.out.println(b+" "+max);
}
return;
}
for(int n = 1;n<=c;n++){
Vector<Integer> tmp = (Vector<Integer>)b.clone();
if(!tmp.contains(n)){
tmp.add(n);
gen(a-1,tmp,c);
}
}
}
}

Saludos
En línea

redinfocol.org
pierrot
pabloN
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 3.348


Ver Perfil
« Respuesta #2 : 28/08/2012, 02:26:43 am »

¡Muchas gracias, Phicar!

Ésto me ha servido mucho:

Ahora, para tu problema, pues usa el arreglo para hacer la inversa...digamos el arreglo más complicado(longitud 10) para el bubble sort sería 10 9 8 7 6 5 4 3 2 1 pero el for de antes lo volverá así

8 9 10 7 4 5 6 3 2 1 luego si lo metes de ésta forma, te quedará ordenado al revés.

No lo había notado  :sonrisa_amplia:.
En línea

$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

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