2x Unidad 1



$SXQWHVGH(VWUXFWXUDGH'DWRV

$XWRU,QJ)HOLSH$ODQtV*RQ]iOH],QVWLWXWR7HFQROyJLFRGH'XUDQJR

$SXQWHVGH(VWUXFWXUDGH'DWRV

8QLGDG $QiOLVLVGH$OJRULWPRV 

&RQFHSWRGH&RPSOHMLGDGGH$OJRULWPRV

3DUDUHVROYHUXQSUREOHPDHVIUHFXHQWHGLVSRQHUGHPiVGHXQDOJRULWPR (O DQiOLVLV GH DOJRULWPRV VLUYH SDUD WHQHU HOHPHQWRV GH GHFLVLyQ SDUD HOHJLU HO PDV HILFLHQWH GH HOORV GHVGH OXHJR VLHPSUH \ FXDQGRODV GLIHUHQWHV RSFLRQHV UHVXHOYDQ HOPLVPRSUREOHPDHQIRUPDFRUUHFWD

(MHPSOR

(VFULEDGRVGLIHUHQWHVSURJUDPDVTXHUHVXHOYDQHOVLJXLHQWHSUREOHPD

‰ ‰

8QDPiTXLQDVHHQFDUJDGHGHWHFWDUFRQWLQXDPHQWHORVPLFURVLVPRV\VLVPRVGHO YROFiQSRSRFDWpSHWO 8VWHG GHEH GLVHxDU GRV GLIHUHQWHV SURFHGLPLHQWRV TXH UHFLEDQ XQ GDWR HQWHUR HQWUH\FRUUHVSRQGLHQWHDXQDPLOpVLPDGHODHVFDODGH5LFKWHULQGLFDWLYR

‰

GHXQPLFURVLVPRGHWHFWDGR 'XUDQWH FLHUWR SHUtRGR GH WLHPSR VH UHFLELUiQ 1 GDWRV \ FDGD SURJUDPD HQFRQWUDUiORVYDORUHVPtQLPR\Pi[LPRDOFDQ]DGRV

/D FRPSOHMLGDG FRPSXWDFLRQDO HV XQD PHGLGD GH ORV UHFXUVRV TXH VH LQYHUWLUiQSDUDLPSOHPHQWDUXQDOJRULWPRHQXQDFRPSXWDGRUD

/RV UHFXUVRV TXH SXHGH VHU GH LQWHUpV FRQWURODU VRQ YDULDGRV VLQ HPEDUJR  HO HQIRTXHJHQHUDOVHFHQWUDHQ

‰ ‰

7LHPSRGH(MHFXFLyQ&RPSOHMLGDGHQHO7LHPSR  (VSDFLRUHTXHULGR&RPSOHMLGDGHQHO(VSDFLR 

(O REMHWLYR GHO DQiOLVLV GH DOJRULWPRV HV FUHDU SURJUDPDV FRQ OD PHQRU FRPSOHMLGDG HVSDFLDO\WHPSRUDO (O UHFXUVR PiV FUtWLFR HV HO 7LHPSR GH HMHFXFLyQ GH XQ SURJUDPD SRU OR TXH HO SUREOHPDSODQWHDGRDUULEDORUHVROYHUHPRVFRQGRVDOJRULWPRV GLVWLQWRVGH GLIHUHQWH FRPSOHMLGDGWHPSRUDOSHURPLVPDFRPSOHMLGDGHQHOHVSDFLR

‰

(O DOJRULWPR GHVGH HO SXQWR GH YLVWD GHO XVR GH OD PHPRULD SDUD DPEDV VROXFLRQHVHVHOPLVPRORVGDWRVREWHQLGRVVHFRQVHUYDQHQXQYHFWRU

‰

/DGLIHUHQFLDHVWULEDHQODIRUPDGHHQFRQWUDUORVYDORUHVPHQRU\PD\RU



$XWRU,QJ)HOLSH$ODQtV*RQ]iOH],QVWLWXWR7HFQROyJLFRGH'XUDQJR

// -------- Solución 1 ------------#include #define LIMINF 1 #define LIMSUP 10000 using namespace std; int main() { int const n=100; short int datos[n]; srand(time(NULL)); for(int i=0;idatos[i+1]) { temp=datos[i]; datos[i]=datos[i+1]; datos[i+1]=temp; hubocambio = true; }; etapa++; } while (hubocambio); // -------- Fin Cálculo de Resultados ----------printf("Dato Menor: %d\n",datos[0]); printf("Dato Mayor: %d\n",datos[n-1]); system("pause"); return 0; }

$SXQWHVGH(VWUXFWXUDGH'DWRV



$XWRU,QJ)HOLSH$ODQtV*RQ]iOH],QVWLWXWR7HFQROyJLFRGH'XUDQJR

// ------------ Solución 2 ------------#include #define LIMINF 1 #define LIMSUP 10000 using namespace std; int main() { int const n=100; short int datos[n]; srand(time(NULL)); for(int i=0;imayor) mayor=datos[i]; } // ------ Inicia Cálculo de Resultados ---------printf("Dato Menor: %d\n",menor); printf("Dato Mayor: %d\n",mayor); system("pause"); return 0; } /$&203/(-,'$'6(38('(2%7(1(5'(0$1(5$6

‰

$35,25,)RUPD7HyULFD 

‰

³$ 3ULRUL´ VLJQLILFD ³DQWHV´ HV GHFLU VH DSOLFD OD WHRUtD GH FRPSOHMLGDG

$XWRU,QJ)HOLSH$ODQtV*RQ]iOH],QVWLWXWR7HFQROyJLFRGH'XUDQJR

(PSH]DUHPRVKDFLHQGRDQiOLVLVGHFRPSOHMLGDGPHGLDQWHHOHQIRTXHHPStULFR

‰

$xDGDDQXHVWURVGRVSURJUDPDVHOFyGLJRQHFHVDULRSDUDPHGLUHOWLHPSRTXHVH

‰

8QRGHORVIDFWRUHVTXHLQIOX\HQHQODFRPSOHMLGDGHVODFDQWLGDGGHGDWRVD

‰

5HJLVWUH HQ XQD WDEOD FRPR OD VLJXLHQWH ORV UHVXOWDGRV TXH VH SLGHQ SDUD FDGD

‰

‰

1R VH WLHQH TXH HVFULELU HO SURJUDPD FRQ HO DKRUUR HQ FRVWRV FRUUHVSRQGLHQWH VH HVFULELUi FXDQGR VH KD\DQ DQDOL]DGR GLIHUHQWHV

‰

DOJRULWPRV\HOHJLGRHOPHMRU (VWHDQiOLVLVHVLQGHSHQGLHQWHGHODVFRQGLFLRQHVGHHMHFXFLyQHVGHFLUQR LPSRUWD VL HO HTXLSR GRQGH FRUUHUi HO SURJUDPD HV UiSLGR R OHQWR HO DOJRULWPRHVHILFLHQWHRQRORHV

‰

$3267(5,25,)RUPD(PStULFD 

‰

³$ 3RVWHULRUL´ VLJQLILFD ³GHVSXpV´ HV GHFLU HVFULELHQGR HO SURJUDPD \ PHGLDQWHODH[SHULHQFLDGHHMHFXFLyQREWHQHUFRQFOXVLRQHV9HQWDMDV

‰ ‰

3RGHPRV KDFHU HO UD]RQDPLHQWR LQYHUVR ¢SRU TXp WRPD WDQWR WLHPSR HVWHSURJUDPD"

(O UD]RQDPLHQWR LQYHUVR HV XQD DOWHUQDWLYD SDUD HVFULELU SURJUDPDV PiV HILFLHQWHV HQFRQWUDPRV XQD VROXFLyQ SUREDEOH OD DQDOL]DPRV \ GHO

DQiOLVLVSXHGHUHVXOWDUXQDPHMRUDSUR[LPDFLyQDOSUREOHPD

HPSOHDSDUDHQFRQWUDUORVUHVXOWDGRVHVSHUDGRV SURFHVDUWDPDxRGHODHQWUDGD HQHVWHFDVR1 XQRGHORVGRVSURJUDPDV &RQVLGHUHVRORHOWLHPSRWUDQVFXUULGRSDUDHQFRQWUDUORVUHVXOWDGRV

7DPDxRGHO

7LHPSR(PSOHDGR

9HFWRU

IUDFFLRQHVGHVHJXQGRVLHV

1

QHFHVDULR

         

2WUR IDFWRU PX\ LPSRUWDQWH TXH LQIOX\H HQ OD FRPSOHMLGDG HV OD QDWXUDOH]D GH ORV GDWRVGHHQWUDGD

‰

'HSHQGLHQGR GH FXDOHV VRQ ORV GDWRV GH HQWUDGD FRPR HVWiQ GLVSXHVWRV ItVLFDPHQWHSRUHMHPSOR FLHUWDVLQVWUXFFLRQHVVHHMHFXWDUiQRQR

FRPSXWDFLRQDODODOJRULWPRSDUDGHWHUPLQDUHOJUDGRGHHILFLHQFLDTXHWHQGUi HOSURJUDPD9HQWDMDV



$SXQWHVGH(VWUXFWXUDGH'DWRV

6XSRQJDPRVTXHEDMRFLHUWDVFRQGLFLRQHV ORVGDWRVHVWiQRUGHQDGRVGH PHQRU DPD\RUFXDQGRVHREWLHQHQODVPHGLFLRQHVGHORVVLVPRV

/XHJRVXSRQJDPRVTXHEDMRRWUDVFRQGLFLRQHVORVGDWRVHVWiQRUGHQDGRV SHUR GH PD\RUDPHQRU

‰

0RGLILTXHDPERVSURJUDPDV\REWHQJDQXHYDVWDEODV,GHQWLILTXHODVWDEODVGHOD IRUPDVLJXLHQWH

‰ ‰ ‰ ‰ ‰ ‰

6ROXFLyQ$OD]DU 6ROXFLyQ


$SXQWHVGH(VWUXFWXUDGH'DWRV

$XWRU,QJ)HOLSH$ODQtV*RQ]iOH],QVWLWXWR7HFQROyJLFRGH'XUDQJR

$SXQWHVGH(VWUXFWXUDGH'DWRV



$XWRU,QJ)HOLSH$ODQtV*RQ]iOH],QVWLWXWR7HFQROyJLFRGH'XUDQJR



$ULWPpWLFDGHODQRWDFLyQ2

6LJXLHQGR FRQ HO HQIRTXH HPStULFR SDUD GHWHUPLQDU ODV GLIHUHQFLDV GH HILFLHQFLD HQWUHDPERVSURJUDPDVDxDGDDFDGDXQRGHHOORVXQFRQWDGRUGHLQVWUXFFLRQHV

‰ ‰ ‰

(OFRQWDGRUVHLQFUHPHQWDUiHQSRUFDGDLQVWUXFFLyQVLPSOHHMHFXWDGD (QWHQGDPRVFRPRLQVWUXFFLyQVLPSOHDXQDDVLJQDFLyQ ODOODPDGD D XQD IXQFLyQ HWF /DV LQVWUXFFLRQHV GHQWUR GHORVFLFORV \ GHQWUR GHODV IXQFLRQHV HQ FDVR GH TXH ODVKXELHUD WDPELpQFXHQWDQFRPR

$QWHVGHLQLFLDUHODQiOLVLVDWUDYpVGHOHQIRTXHWHyULFRUHYLVHPRVORVUHVXOWDGRV REWHQLGRVGHODQiOLVLVHPStULFRDSDUWLUGHORVSURJUDPDVVLJXLHQWHV

// Programa 1 #include #define LIMINF 1 #define LIMSUP 10000 using namespace std;

int main() { int const n=10000; short int datos[n]; srand(time(NULL));

/* for(int i=0;i
(MHFXWHGHQXHYRHOSURJUDPDUHSRUWDQGRHOYDORUGHOFRQWDGRU 0RGLILTXHODVWDEODV\DFUHDGDVSDUDUHJLVWUDUORVQXHYRVGDWRV

7DPDxRGHO

1~PHURGH

7LHPSR(PSOHDGR

9HFWRU

,QVWUXFFLRQHV

IUDFFLRQHVGHVHJXQGRVLHV

1

(MHFXWDGDV

QHFHVDULR

  

// ------ Inicia Cálculo de Resultados ----------



double contador=0;



int temp; int etapa = 1; bool hubocambio; contador += 3; do { hubocambio = false;

   

contador += 2; //la declaración “int i=0” también cuenta



for(int i=0;i
contador++; if (datos[i]>datos[i+1]) {

&DVR0HMRU

(OWLHPSRGHHMHFXFLyQ\ODFDQWLGDGGHLQVWUXFFLRQHVHMHFXWDGDVVRQORVPtQLPRV

contador += 4; temp=datos[i]; datos[i]=datos[i+1]; datos[i+1]=temp; hubocambio = true; };

&DVR3HRU

(OWLHPSRGHHMHFXFLyQ\ODFDQWLGDGGHLQVWUXFFLRQHVHMHFXWDGDVVRQORVPi[LPRV

&DVR3URPHGLR

} etapa++; contador += 2; // etapa++ y while } while (hubocambio); // ------ Fin Cálculo de Resultados ----------

(OWLHPSRGHHMHFXFLyQ\ODFDQWLGDGGHLQVWUXFFLRQHVHMHFXWDGDVFDHQHQFLHUWR YDORU LQWHUPHGLR

final = clock(); printf("Tiempo Transcurrido: %10.3f seg\n", float(final-inicial)/CLOCKS_PER_SEC); printf("Contador : %f\n",contador); printf("Dato Menor: %d\n",datos[0]); printf("Dato Mayor: %d\n",datos[n-1]); system("pause"); return 0; }

$SXQWHVGH(VWUXFWXUDGH'DWRV



$XWRU,QJ)HOLSH$ODQtV*RQ]iOH],QVWLWXWR7HFQROyJLFRGH'XUDQJR

// Programa 2 #include #define LIMINF 1 #define LIMSUP 10000 using namespace std; int main() { int const n=500000; short int datos[n]; srand(time(NULL)); // semilla

/* for(int i=0;i
contador += 2; for(int i=0;i
contador += 2; // los 2 if if (datos[i]<menor) {menor=datos[i];contador++; } if (datos[i]>mayor) {mayor=datos[i];contador++; } } // ------ Fin Cálculo de Resultados ----------

final = clock(); printf("Tiempo Transcurrido: %10.3f seg\n", float(final-inicial)/CLOCKS_PER_SEC); printf("Contador : %f\n",contador); printf("Dato Menor: %d\n",menor); printf("Dato Mayor: %d\n",mayor); system("pause"); return 0; }



$SXQWHVGH(VWUXFWXUDGH'DWRV

$XWRU,QJ)HOLSH$ODQtV*RQ]iOH],QVWLWXWR7HFQROyJLFRGH'XUDQJR

PROGRAMA 1 DATOS ALEATORIOS N Contador Tiempo 1,000 1,497,318 0.06 2,000 6,038,834 0.33 5,000 37,422,768 0.94 10,000 149,026,394 3.52 20,000 602,414,994 13.34 50,000 3,739,551,608 79.59 100,000 14,974,791,796 293.52 200,000 500,000 1,000,000

PROGRAMA 1 DATOS ORDENADOS N Contador Tiempo 1,000 1,006 0 2,000 2,006 0 5,000 5,006 0 10,000 10,006 0 20,000 20,006 0 50,000 50,006 0 100,000 100,006 0 200,000 200,006 0 500,000 500,006 0 1,000,000 1,000,006 0.06

PROGRAMA 1 DATOS ORDENADOS A LA INVERSA N Contador Tiempo 1,000 2,501,503 0.06 2,000 10,003,003 0.11 5,000 62,507,503 0.87 10,000 250,012,723 3.08 20,000 999,987,727 11.65 50,000 6,249,672,724 73.98 100,000 24,998,347,699 304.73 200,000 500,000 1,000,000

&DVR 3URPHGLR

HARDWARE Y SOFTWARE: PENTIUM III 700 MHZ 128 RAM WINDOWS 98SE DEV C++ 4.9.9.1

0HMRU &DVR

3HRU &DVR

3DUDWRPDUORVGDWRV IDOWDQWHVVHWHQGUtDTXH HPSOHDUPXFKRWLHPSR ¢FXiQWR"



$SXQWHVGH(VWUXFWXUDGH'DWRV

$XWRU,QJ)HOLSH$ODQtV*RQ]iOH],QVWLWXWR7HFQROyJLFRGH'XUDQJR



$SXQWHVGH(VWUXFWXUDGH'DWRV

$XWRU,QJ)HOLSH$ODQtV*RQ]iOH],QVWLWXWR7HFQROyJLFRGH'XUDQJR

3RGHPRVH[SUHVDUORVOtPLWHVGHFRPSRUWDPLHQWRGHO 3URJUDPDBHQWpUPLQRVGH

N 1,000 2,000 5,000 10,000 20,000 50,000 100,000 200,000 500,000 1,000,000

PROGRAMA 2 DATOS ALEATORIOS Contador 2,020 4,019 10,019 20,022 40,020 100,020 200,020 400,024 1,000,024 2,000,017

XQSROLQRPLRODVH[SUHVLRQHVVHSXHGHQREWHQHUGHODREVHUYDFLyQGHODVWDEODV\HO SURJUDPD 

Tiempo 0 0 0 0 0 0 0 0 0 0.06

0HMRU&DVR

0HMRU &DVR

(n -1) + 7

Æ

n+6

Æ

2.5n2 + 1.5n + 3

3HRU&DVR

5n(n-1)/2 + 4n + 3

HVWHSROLQRPLRHVFRUUHFWRVLHPSUH\FXDQGRSDUDFXDOTXLHUWDPDxRGH 1ORVGDWRVVHDQWRGRVGLIHUHQWHV\GHVGHOXHJRVHHQFXHQWUHQ

N 1,000 2,000 5,000 10,000 20,000 50,000 100,000 200,000 500,000 1,000,000

PROGRAMA 2 DATOS ORDENADOS Contador 3,002 6,002 15,002 29,432 50,002 110,002 210,002 410,002 1,010,002 2,010,002

RUGHQDGRVDODLQYHUVD

Tiempo 0 0 0 0 0 0 0 0 0.06 0.11

PROGRAMA 2 DATOS ORDENADOS A LA INVERSA N Contador Tiempo 1,000 3,002 0 2,000 6,002 0 5,000 15,002 0 10,000 29,432 0 20,000 50,003 0 50,000 110,003 0 100,000 210,003 0 200,000 410,003 0 500,000 1,010,003 0.05 1,000,000 2,010,003 0.06

3DUDHO3URJUDPDSRGHPRVHVWDEOHFHUXQOtPLWHSDUDHOSHRUFDVRSHURQRSDUD HOPHMRUFDVR\DTXHHVWH~OWLPRHVFRQORVGDWRVDOD]DU 

3HRU&DVR

3n + 2 $ HVWH WLSR GH SUREOHPDV VH OHV OODPD SUREOHPDV 3 3ROLQyPLFRV  1R WRGRV ORV PLHPEURVGHHVWHFRQMXQWRGHSURJUDPDVVRQPX\HILFLHQWHV

3HRUHV &DVRV

‰

‰

/RV OLQHDOHV

VRQ ORV

PiV

HILFLHQWHV

VRQ ORV

TXH VLHPSUH EXVFDQ

ORV

SURJUDPDGRUHV /RV SUREOHPDV SROLQyPLFRV GH VHJXQGR JUDGR R PD\RU VH HQFXHQWUDQ HQ ORV ³OtPLWHV GH OR WUDWDEOH´ HQWHQGDPRV SRU HVWR TXH EDMR FLHUWDV FRQGLFLRQHV VH

SXHGHQUHVROYHUHQXQWLHPSRUD]RQDEOHEDMRRWUDVFRQGLFLRQHVQR

‰

¢3RUTXp"

‰ ‰

3RUTXH XQD YH] TXH XQ SURJUDPD VH GHPXHVWUD TXH HV ~WLO  VH XVDUi SDUDSUREOHPDVFDGDYH]PiVJUDQGHV /D PDJQLWXG GH ORV SURJUDPDV GHSHQGH JHQHUDOPHQWH GH XQD

HVWUXFWXUDTXHHVWiHQIXQFLyQGHXQDYDULDEOHTXHFRP~QPHQWHOODPDPRV

‰

1

3RU OR WDQWR VH GHEH SHQVDU HQ TXH XQ SURJUDPD GHEH VHU HILFLHQWH SDUD UHVROYHU SUREOHPDV GH PDJQLWXG FUHFLHQWH (V GHFLU FXDQGR 1 WLHQGH D LQILQLWR

2EVHUYH TXH ORV H[SHULPHQWRV DUULED GH  GDWRV VREUH WRGR DO EXVFDU ORV OtPLWHVSXHGHQVHUHQJDxRVRVSRUTXHVHSURGXFHQ PXFKRVGDWRVUHSHWLGRV SDUD HVWHSUREOHPDSDUWLFXODURWURLQFRQYHQLHQWHGHOHQIRTXHHPStULFRSXUR 

‰ ‰ ‰

2VHDTXHVH FODVLILFDQORV DOJRULWPRV GH DFXHUGR D VX FRPSRUWDPLHQWR DVLQWyWLFR

$OJUXSRGHDOJRULWPRVTXHFRPSDUWHQHOPLVPRFRPSRUWDPLHQWRDVLQWyWLFR VHGLFHTXHSHUWHQHFHQDOPLVPRRUGHQGHFRPSOHMLGDG (ORUGHQGHFRPSOHMLGDGVHGHQRPLQDQRWDFLyQ2



$SXQWHVGH(VWUXFWXUDGH'DWRV

$XWRU,QJ)HOLSH$ODQtV*RQ]iOH],QVWLWXWR7HFQROyJLFRGH'XUDQJR



$SXQWHVGH(VWUXFWXUDGH'DWRV

$XWRU,QJ)HOLSH$ODQtV*RQ]iOH],QVWLWXWR7HFQROyJLFRGH'XUDQJR 6HJXQGR VL HO WDPDxR Q GHO SUREOHPD DSDUHFH FRPR OtPLWH GHO FLFOR SXHGHQ

GDUVHYDULRVFDVRV (Q JHQHUDO QR HV QHFHVDULR FRQRFHU HO FRPSRUWDPLHQWR H[DFWR GH XQ DOJRULWPR VLQR VRORVXOtPLWHGHFRPSRUWDPLHQWRHVGHFLUODFRWDRDFRWDPLHQWRVXSHULRU

Æ∞

8Q FLFORR FLFORV DQLGDGRVFRQ XQD VHFXHQFLDGH LQVWUXFFLRQHV VLPSOHV HQ VX LQWHULRU

&RPRHODQiOLVLVDVLQWyWLFRLPSOLFDTXHORLPSRUWDQWHHVHOFRPSRUWDPLHQWRFXDQGR 1



HOJUDGRGHOSROLQRPLRHVORTXHGHWHUPLQDHORUGHQ GH FRPSOHMLGDG HV GHFLU

SDUDHOSROLQRPLRTXHREWXYLPRVHPStULFDPHQWHSDUDHOSHRUFDVRGHODVROXFLyQ

Q 2  Q Q 2  Q 2Q 



2.5n2 + 1.5n + 3

Q 2Q  Q Q Q 2 

Î Î Î Î Î



2Q



2Q

  

  2Q  2Q



2Q

ODFRQVWDQWHPXOWLSOLFDWLYDGHOWpUPLQRGHPD\RUJUDGRHOWpUPLQROLQHDO \ HO WpUPLQR LQGHSHQGLHQWHVHKDFHQGHVSUHFLDEOHVFXDQGR1WLHQGHDLQILQLWR 3RU OR WDQWR VH GLFH TXH HVH DOJRULWPR \ HO SURJUDPD HTXLYDOHQWH VRQ GH RUGHQ



2Q 

8Q FLFOR VH UHDOL]D 1 YHFHV HVWH FRQWLHQH RWUR FLFOR HQ VX LQWHULRU TXH VH HMHFXWD  YH] OD SULPHUD  YHFHV OD VHJXQGD  YHFHV OD WHUFHUD \ DVt VXFHVLYDPHQWH KDVWD 1 YHFHV 'HQWUR GHO VHJXQGR FLFOR KD\ XQD VHFXHQFLD VLPSOHGHLQVWUXFFLRQHV

(OSROLQRPLRGHSULPHUJUDGRFRUUHVSRQGLHQWHDODVROXFLyQSHRUFDVR 

3n – 2HQFRQVHFXHQFLDVHUiGHRUGHQ2Q  ¢&yPRREWHQHU$35,25,ODFRPSOHMLGDGGHXQDOJRULWPR\SRUORWDQWR GHOSURJUDPDHTXLYDOHQWH"

Q Q  2 

Î





2Q

&LFORVHQORVTXHHOFRQWDGRUWLHQHXQYDORULQLFLDOGH\GHEH OOHJDU D 1 SHUR PXOWLSOLFiQGRVH SRU XQD FRQVWDQWH \ HQ VX LQWHULRU KD\ XQD VHFXHQFLD VLPSOH GHLQVWUXFFLRQHV

1R H[LVWH XQD UHFHWD LQIDOLEOH VLQ HPEDUJR KD\ FLHUWDV UHJODV TXH GDQ PX\

(MHPSOR

EXHQRV UHVXOWDGRV DVXPLHQGR TXH ORV DOJRULWPRV SRVHDQ XQD HVWUXFWXUD XQLIRUPH\FODUD

F



ZKLOHF1

D ,QVWUXFFLRQHV6HQFLOODV 7RGDV DTXHOODVLQVWUXFFLRQHV GH GHFODUDFLyQ HQWUDGD \ VDOLGD DVLJQDFLyQ TXH QR GHSHQGDQGHOWDPDxR1GHOSUREOHPD7RGDVHOODVVRQGHRUGHQ2 HVGHFLU

VRQGHRUGHQFRQVWDQWH\VLHPSUHVHHMHFXWDUiODPLVPDFDQWLGDGGHHOODV

E &LFORV

F

Î

F 

LQVWUXFFLRQHVGHRUGHQ2

2ORJQ

(MHPSOR &LFORVHQORVTXHHOFRQWDGRUWLHQHXQYDORULQLFLDOGH1\GHEH OOHJDU D  SHUR GLYLGLpQGRVH VXFHVLYDPHQWH SRU XQD FRQVWDQWH \ HQ VX LQWHULRU KD\ XQD VHFXHQFLDVLPSOHGHLQVWUXFFLRQHV

'HEHPRVFRQVLGHUDUFDVRV

3ULPHURVLHOFLFORVHHMHFXWDXQFLHUWRQ~PHURGHYHFHVSHURLQGHSHQGLHQWHGHO

(MHPSOR

WDPDxRQGHOSUREOHPDHQWDOFDVRVRORVHLQYROXFUDDXQDFRQVWDQWH F (MHPSORV

N 2  N 2Q 

Î Î

1

ZKLOHF!



2



2Q

Î



F

F

LQVWUXFFLRQHVGHRUGHQ2

2ORJQ



$SXQWHVGH(VWUXFWXUDGH'DWRV

$XWRU,QJ)HOLSH$ODQtV*RQ]iOH],QVWLWXWR7HFQROyJLFRGH'XUDQJR

$XWRU,QJ)HOLSH$ODQtV*RQ]iOH],QVWLWXWR7HFQROyJLFRGH'XUDQJR

F -HUDUTXtD



/RV yUGHQHV GH FRPSOHMLGDG VH DJUXSDQ MHUiUTXLFDPHQWH \D TXH ORV RUGHQHV PHQRUHVHVWiQWRGRVDFRWDGRVSRUORVPD\RUHV



$SXQWHVGH(VWUXFWXUDGH'DWRV



&RPSOHMLGDG

7LHPSRGHHMHFXFLyQGHXQDOJRULWPR

2

&RQVWDQWH

0LHQWUDV PiV JUDQGH HV HO SUREOHPD HO RUGHQ GH FRPSOHMLGDG DVLQWyWLFD HV PiV

2ORJQ

/RJDUtWPLFR

SUy[LPR DO FRPSRUWDPLHQWR UHDO 3RU OR WDQWR ODV REVHUYDFLRQHV HPStULFDV QRV

2Q

/LQHDO

2QORJQ

&XDVL/LQHDO

2Q

&XDGUiWLFR

2Q

&XEtFR

  N

SXHGHQ VHUYLU SDUD KDFHU SUR\HFFLRQHV GHO WLHPSR TXH WDUGDUi XQ DOJRULWPR SDUD

7UDEDMHPRVGHQXHYRFRQODWDEODGHOFDVRSURPHGLRREWHQLGDDQWHULRUPHQWH

2Q N!

3ROLQyPLFR

2N N!

([SRQHQFLDO

2Q

)DFWRULDO

Q

FXDOTXLHUWDPDxRGHSUREOHPD

HARDWARE Y SOFTWARE EMPLEADO PENTIUM III 700 MHZ 128 RAM WINDOWS 98SE DEV C++ 4.9.9.1

G 6HFXHQFLDV 2EWHQJDPRVXQSDUGHFRQVWDQWHV.\. TXHLQGLTXHQODUHODFLyQHQWUHHOQ~PHUR (Q ODV VXPDV GHO SROLQRPLR FRUUHVSRQGLHQWH D XQ DOJRULWPR XQ RUGHQ VXSHULRU ³DEVRUEH´ DO LQIHULRU \ OD VXPD GH RUGHQHV GH OD PLVPD MHUDUTXtD HTXLYDOHQ DO PLVPRRUGHQ (MHPSORV



2 2Q 2Q  2 2 2  2Q 2Q 2Q 

Î Î Î



ODGR





2Q



2



2Q

H 'HFLVLRQHVLI  /DHYDOXDFLyQGHOD FRQGLFLyQ JHQHUDOPHQWH HV GH RUGHQ 2  FRPSOHMLGDG TXH VH VXPDUi FRQ OD SHRU GH ODV  UDPDV GHO LI VHD GHO WKHQ R HO HOVH

VLJXLHQGRODVUHJODVGHODVHFXHQFLDV



GHLQVWUXFFLRQHVHMHFXWDGDV\ 1 SRUXQODGR\HOWLHPSRGHHMHFXFLyQ\ 1 SRURWUR

N 1,000 2,000 5,000 10,000 20,000 50,000 100,000 200,000 500,000 1,000,000

PROGRAMA 1 CASO PROMEDIO DATOS ALEATORIOS K1 = Contador Tiempo Contador / N2 1,497,318 0.06 1.49731800 6,038,834 0.33 1.50970850 37,422,768 0.94 1.49691072 149,026,394 3.52 1.49026394 602,414,994 13.34 1.50603749 3,739,551,608 79.59 1.49582064 14,974,791,796 293.52 1.49747918 59,899,167,184 1,174.08 374,369,794,900 7,338.00 1,497,479,179,600 29,352.00

K2 = Tiempo / N2 0.000000060000 0.000000082500 0.000000037600 0.000000035200 0.000000033350 0.000000031836 0.000000029352

I 3URFHGLPLHQWRV /DFRPSOHMLGDGGHODOODPDGDGHXQSURFHGLPLHQWRHV 2 SHURODFRPSOHMLGDG

(O KHFKR GH TXH ORV YDORUHV GH . \ . SHUPDQHFHQ SDUD ILQHV SUiFWLFRV

GHO SURFHGLPLHQWR HQ Vt VH FDOFXOD GH DFXHUGR D ODV LQVWUXFFLRQHV FRQWHQLGDV HQ

SUiFWLFDPHQWH FRQVWDQWHV QRV LQGLFD TXH HO WLHPSR GH HMHFXFLyQ HV SURSRUFLRQDO

pOEDViQGRQRVHQHVWDVPLVPDVUHJODV



SDUDHVWHDOJRULWPRD1 ORTXHQRVSHUPLWHKDFHUSUHGLFFLRQHVGHOFRPSRUWDPLHQWR SDUD YDORUHV GH 1 PX\ JUDQGHV TXH QR GHVHDPRV R QR SRGHPRV REWHQHU GH IRUPD

&RPSUXHEH VLJXLHQGR ODV UHJODV TXH DFDEDPRV GH HVWDEOHFHU TXH ORV RUGHQHV GH

HPStULFD

FRPSOHMLGDGDVLQWyWLFDGHORVSUREOHPDVGHOLQLFLRGHHVWHWHPDVRQ 5HDOLFHVLPLODUHVSUHGLFFLRQHVSDUDODWDEODGHO3HRU&DVR\FRPSUREDUiTXHOD~QLFD



6ROXFLyQ

2Q

6ROXFLyQ

2Q

GLIHUHQFLDVRQORVYDORUHVGHODVFRQVWDQWHV.\.

$SXQWHVGH(VWUXFWXUDGH'DWRV





$SXQWHVGH(VWUXFWXUDGH'DWRV

$XWRU,QJ)HOLSH$ODQtV*RQ]iOH],QVWLWXWR7HFQROyJLFRGH'XUDQJR

$XWRU,QJ)HOLSH$ODQtV*RQ]iOH],QVWLWXWR7HFQROyJLFRGH'XUDQJR



8QDGHODVSULPHUDVDSUR[LPDFLRQHVSDUDPHMRUDUORVDOJRULWPRVGHRUGHQDPLHQWRGH

&RPSOHMLGDGHQHOHVSDFLR

/D &RPSOHMLGDG (VSDFLDO VH UHILHUH DO HVSDFLR GH PHPRULD TXH XQ DOJRULWPR UHTXHULUiGXUDQWHVXHMHFXFLyQ 3XHGH VHU PHPRULD 5$0 R FXDOTXLHU PHGLR $OPDFHQDPLHQWR 6HFXQGDULR ORV GLVFRVGXURVSRUHMHPSOR 

6HPLGHGHIRUPDPX\VLPLODUDODFRPSOHMLGDGWHPSRUDO

‰

1RWLHQHLPSDFWR

‰

‰

/D FDQWLGDG GH GDWRV LQGLYLGXDOHV TXH QR GHSHQGH GH 1 (MHPSOR SDUiPHWURVGHODVIXQFLRQHVH[FHSWRYHFWRUHVSRUYDORU  /DV HVWUXFWXUDV GH GDWRV YHFWRUHV OLVWDV HQFDGHQDGDV HWF  FX\R WDPDxR QRGHSHQGHGH 1(MHPSORHO WDPDxR GHO GLFFLRQDULR TXH VH XVD SDUD UHYLVDU

‰

‰

ODRUWRJUDItDGHXQWH[WR /DHVWUXFWXUDOyJLFDGHODOJRULWPR(MHPSORV

‰ ‰ ‰ ‰ ‰

'HFODUDFLRQHVGHYDULDEOHV &XDQWRVFLFORVRFXDQWDVYHFHVVHHMHFXWDQ 6LORVFLFORVHVWiQDQLGDGRVRQR /ODPDGDVDHMHFXFLyQGHIXQFLRQHV

6LWLHQHLPSDFWR

‰

‰

/DFDQWLGDGGHGDWRVTXHGHSHQGHQGH1

‰

(VWH PpWRGR DSOLFD GH PDQHUD PX\ VHQFLOOD XQD WpFQLFD FRQRFLGD FRPR ³'LYLGH \ 9HQFHUiV´

'LVWULEXFLyQ6LPSOHVXJLHUH

‰ ‰ ‰

'LYLGLUGHFLHUWDIRUPDHODUFKLYRJUDQGHHQYDULDVSDUWHVSHTXHxDV /DVSDUWHVVHRUGHQDQSRUVHSDUDGR /DVSDUWHVVHXQHQXQDGHVSXpVGHRWUD

/RVDUFKLYRVSHTXHxRVVHRUGHQDQFRQPHQRVHVIXHU]RTXHORVJUDQGHVSDUDRUGHQHV GHFRPSOHMLGDGWHPSRUDOVXSHULRUHVD2Q 

8Q YHFWRU DX[LOLDU TXH XVHPRV SDUD FDGD  GDWRV SRU HMHPSOR  GH XQ YHFWRUGHWDPDxR1

/RV SDUiPHWURV GH YDORU TXH GHSHQGHQ GHO WDPDxR 1  \D TXH HQ OD PHPRULDVHKDFHXQDFRSLDGHORVGDWRV



$SR\iQGRQRVHQODWDEODGHOFDVRSURPHGLRGHOPpWRGRGHODEXUEXMD2Q 

DUFKLYRGH¶UHJLVWURV

¶¶LQVWUXFFLRQHV

0LVPRDUFKLYRGLYLGLGRHQVXEDUFKLYRVXQRSRUOHWUDGHODOIDEHWR

‰ ‰ ‰

1~PHURGHUHJLVWURV[VXEDUFKLYR

DSUR[

,QVWUXFFLRQHVSDUDRUGHQDUFVXEDUFKLYR

¶HVWLPDGDV

,QVWUXFFLRQHVHQWRWDO

¶[ ¶DSUR[

(WF

/RV SDUiPHWURV SRU UHIHUHQFLD \D TXH QR VH UHTXLHUH HVSDFLR H[WUD SDUD HOORV

‰



RUGHQ2Q IXHXQPpWRGRFRQRFLGRFRPR'LVWULEXFLyQ6LPSOH

&RPRSRGHPRVYHU HO Q~PHUR GH LQVWUXFFLRQHV HMHFXWDGDV GLVPLQX\H HQ SURSRUFLyQ DOQ~PHURGHVXEDUFKLYRV0LOORQHVGH0LOORQHVFRQWUD0LOORQHV

3RU OR WDQWR IRUPDQGR  VXEDUFKLYRV HQ EDVH D OD SULPHUD OHWUD GH OD &853 VH UHGXFLUtD HO WLHPSR GH HMHFXFLyQ D  GtDVR VHD OD  SDUWH GH  DxRV ¢QDGD PDOSDUDHPSH]DUHK" 



6L WRPDPRV ODV  OHWUDV SULPHUDV HQWRQFHV VHUtDQ WHyULFDPHQWH   VXEDUFKLYRV   (Q UHDOLGDG OD VHJXQGD OHWUD VLHPSUH HV XQD YRFDO SRU OR TXH HO Q~PHUR GH

3UREOHPD



VXEDUFKLYRVTXHFRQIRUPDUtDPRVVHUtD [ 

6HFXHQWDFRQXQDFLQWDPDJQpWLFDTXHFRQWLHQHORVGDWRVGHWRGRVORVKDELWDQWHVGH

&RPR WHyULFDPHQWH OD GLVWULEXFLyQ GH ORV GDWRV VHUi XQLIRUPH HO WDPDxR SURPHGLR

ORV(VWDGRV8QLGRV0H[LFDQRVGLJDPRV 0LOORQHVHQQ~PHURVUHGRQGRV \VH

GHFDGDVXEDUFKLYRVHUiGHUHJLVWURV

EXVFD RUGHQDUORV HQ EDVH D VX Q~PHUR GH &853 VL DSOLFDPRV HO PpWRGR GH OD EXUEXMDTXHFRQRFHPRVHOWLHPSR GH HMHFXFLyQ HQ ODFRPSXWDGRUD TXH VH XVy SDUD QXHVWURVH[SHULPHQWRVVHUtD£DxRV¢TXpSRGUtDPRVKDFHU"

&DGD VXEDUFKLYR GH  UHJLVWURV RFDVLRQDUiQ XQ WLHPSR GH  VHJXQGRV \ DO DFXPXODU HO WLHPSR LQGLYLGXDO GH WRGRV HOORV HO WLHPSR WRWDO VHUtD  PLQXWRV« WHyULFDPHQWH

7HyULFDPHQWH SRUTXH DO WUDWDUVH GH VXEDUFKLYRV GH WDPDxR PX\ SHTXHxR HO WLHPSR GH HMHFXFLyQ GH VXV LQVWUXFFLRQHV \ VHFXHQFLDV GH RUGHQ GH FRPSOHMLGDG WHPSRUDO 2  \ 2Q  \D QR HV GHVSUHFLDEOH \ OD SUHGLFFLyQ QR VHUi PX\ H[DFWD

$SXQWHVGH(VWUXFWXUDGH'DWRV



$XWRU,QJ)HOLSH$ODQtV*RQ]iOH],QVWLWXWR7HFQROyJLFRGH'XUDQJR



$SXQWHVGH(VWUXFWXUDGH'DWRV

$XWRU,QJ)HOLSH$ODQtV*RQ]iOH],QVWLWXWR7HFQROyJLFRGH'XUDQJR

DXQTXH VXILFLHQWH SDUD WRPDU GHFLVLRQHV 6H SXHGH REWHQHU HO SROLQRPLR GHO DOJRULWPR FRUUHVSRQGLHQWH \ HQ EDVH D pO KDFHU XQD SUHGLFFLyQ PDV FHUFDQD D OD UHDOLGDG 

(V 3HUWLQHQWH PHQFLRQDU TXH OD FRPSOHMLGDG GH 'LVWULEXFLyQ 6LPSOH VLQ LPSRUWDU HO

 Q~PHURGHVXEDUFKLYRVVLJXH VLHQGR 2Q  \D TXH FXDQGR 1

∞OD FRQVWDQWH TXH



6(/(&&,Ï1'(81$/*25,702

/RVPHMRUHVDOJRULWPRVVRQDTXHOORVTXHSRVHHQFRPRPi[LPRXQ HTXLOLEULR HQWUH OD &RPSOHMLGDG7HPSRUDO \ OD &RPSOHMLGDG (VSDFLDO (V GHFLU TXH VDFULILFDQ WLHPSR SRU HVSDFLRRYLFHYHUVD

UHSUHVHQWDDOQ~PHURGHVXEDUFKLYRVVHUiGHVSUHFLDEOHQRREVWDQWHSXGLHQGRUHVLVWLU YDORUHVGH1PD\RUHV

6LHPSUHVHSXHGHVHOHFFLRQDUXQDOJRULWPRFRPRHOGH'LVWULEXFLyQ6LPSOHTXHFRPR YLPRV ORJUD EDMDU FRQ SRFR HVIXHU]R HO WLHPSR GH SURFHVDPLHQWR GHVGH  DxRV

&RQ HO DQiOLVLV DQWHULRU YHPRV TXH VH SXHGH REWHQHU XQD PHMRUtD VXVWDQFLDO FRQ

KDVWDGtDV\FRQXQSRFRGHPiVHVIXHU]RDPLQXWRV

UHVSHFWR DO WLHPSR GH HMHFXFLyQ SHUR D FDPELR GH XQ DXPHQWR GH OD FRPSOHMLGDG HVSDFLDO

6LQ HPEDUJR DXQTXH HQ OD SUDFWLFD SXHGH VHU GH FLHUWD D\XGD OD FRPSOHMLGDG



WHPSRUDO GH XQ DOJRULWPRFRPR HO GH 'LVWULEXFLyQ 6LPSOH DO VHU 2Q  QR GHMD GH ¢3RUTXpKD\XQDXPHQWRHQODFRPSOHMLGDGHVSDFLDO" 3RUTXHVHUHTXLHUHHVSDFLRH[WUDSDUDFRQVHUYDUORVGDWRV\UHVROYHUHOSUREOHPD

‰

6L VH JXDUGDQ HQ 9HFWRUHV HO RUGHQ GH FRPSOHMLGDG HVSDFLDO GH OD VROXFLyQ HV PLVPRDUFKLYR 6LVHJXDUGDQHQ /LVWDV(QFDGHQDGDVQR VH UHTXHULUi WDQWR HVSDFLR VROR SDUD HO HTXLYDOHQWH DO PLVPR DUFKLYR PiV HO HVSDFLR QHFHVDULR SDUD ORV DSXQWDGRUHV GHOVXFHVRUGHFDGDQRGR1DSXQWDGRUHV 

‰

/DVROXFLyQHVGHILQLWLYDPHQWHEXVFDUDOJRULWPRVFRQRUGHQGHFRPSOHMLGDGWHPSRUDO



LQIHULRU D 2Q  < HQ FXDQWR D OD FRPSOHMLGDG HVSDFLDO FRQYLHQH TXH VHDQ FRPR PX\ DOWR \ SRU OR WDQWR PX\ PDOR VH UHTXHULUtD  YHFHV HO HVSDFLR GHO

‰

VHUPX\DOWD

(Q 'LVFRV'XURVVHUtD XQD VLWXDFLyQ VLPLODU D ODV OLVWDV HQFDGHQDGDV SHUR LJXDO TXHpVWDVVHUHTXHULUtDOOHYDUXQ FRQWURO GH GLUHFFLRQHV SDUD SRGHU DFFHGHU D ORV GDWRVRUJDQL]DGRVHQVXEDUFKLYRVLQGHSHQGLHQWHV

Pi[LPR GH RUGHQ 2Q ORJ Q  HV GHFLU TXH QR UHTXLHUDQ HVSDFLR H[WUD HQ IRUPD LPSRUWDQWH