Pr ctica 1 DA

˜ de algoritmos
Diseno
2014 - 2015

Pr´actica de Programaci´on 1
Mikel Dalmau
8 de Marzo de 2015
Resumen
En la siguiente pr´
actica se realiza un estudio anal´ıtico y experimental de varias de las distintas soluciones
para el problema de hallar un segmento de suma m´
axima en una secuencia de enteros.

1

Soluci´
on c´
ubica

La siguiente soluci´
on explora todos los segmentos posibles de lasecuencia, realiza una nueva suma para cada
segmento y compara dicho valor con el maximo alcanzado hasta el momento.

1.1

Estudio anal´ıtico

El c´
odigo del algoritmo es el siguiente:
void segSumaMaxH ( string fname ) {
vector < int > V ;
int n ,i ,j ,k , sum , maxSum , start , end ;
leerFichero ( fname , &V , & n ) ;
maxSum = V [0]; start = 0; end = 0;
for ( i = 0; i < n ; i ++) {
for ( j = i ; j sum = 0;
for ( k = i ; k < j +1; k ++) {
sum = sum + V . at ( k ) ;
if ( sum > maxSum ) {
maxSum = sum ;
start = i ;
end = j ;
}
}
}
}
cout << start << " " << end - 1 << " " << maxSum << endl ;
};

Observando el c´
odigo podemos ver que realiza 3 bucles y un acceso al vector por cada iteraci´on del bucle de
mas al interior, el resto de operaciones son de orden constante, y el accesoal vector es tambi´en de complejidad
constante [cppRef]. La funci´
on de coste de este algoritmo es entonces de la siguiente forma:
n

n

j

f (n) =

1
i=1 j=1 k=i

˜
Ano:
Profesor(a):
´
Telefono:
E-mail:

2014 - 2015
Jess Bermudez De Andres
mdalmau002@ikasle.ehu.es

GIPUZKOAKO CAMPUSA
CAMPUS DE GUIPUZCOA
Paseo Manuel de Lardizabal, 1
20018 Donostia (Gipuzkoa)

˜ de algoritmos
Diseno
2014 - 2015n

n

n

(j − i + 1) =

f (n) =
i=1 j=1

1
2

n−1

(1 + 2 + ... + (n − i + 1)) =
i=1

=
=

n

k+
k=1

1

k + ... +
k=1

k=
k=1

2×1
(n + 1)n (n − 1)n (n + 1)(n − 2)
+
+
+ ... +
=
2
2
2
2

n

k(k + 1) = f (n − 1) +
k=1

(n + 1)n
(n + 2)(n + 1)n
=
≡ O(n3 )
2
6

Vemos que finalmente la soluci´
on resulta ser de orden c´
ubico y ya pod´ıa intuirse por el hecho de contener 3
bucles uno dentro de otro.1.2

Estudio experimental

El lenguaje de programaci´
on utilizado para las pruebas de los algoritmos ha sido c++, la computadora es
una HP pavilion dv7 con procesador AMD 2.8 Ghz y arquitectura de 64 bits.
El tama˜
no de las pruebas realizadas con cada algoritmo var´ıa dependiendo del tiempo de computo de cada
uno, de forma que hubiera suficientes datos para distinguir el orden de crecimiento yse terminaran en un tiempo
razonable.
Para indicar el tama˜
no de entrada se ha utilizado la siguiente notaci´on (1000 enteros = 1K). Se ha realizado
tres pruebas para cada algoritmo con tama˜
nos iguales pero entradas distintas en cada una, luego se ha realizado
una media de las pruebas.

N (K)
1
2
4
8
10

T(s) Prueba1
3.51
27.55
218.027
1732.55
3410.31

T(s) Prueba2
3.167
25.975
198.5271684.421
3280.897

T(s) Prueba3
3.213
24.227
205.672
1761.954
3457.159

media
3.297
25.917
207.408
1726.308
3382.788

√
3

media
1.488
2.959
5.919
11.995
15.012

Tabla 1: Tiempos soluci´on c´
ubica.

En las siguientes gr´
aficas podemos apreciar el crecimiento cuadr´atico del tiempo de c´omputo, y como al hacer
la ra´ız de estos valores la funci´
on se hace lineal.

2

˜ de algoritmos
Diseno
2014 - 2015Figura 1: Representaci´on gr´afica de los datos de la tabla 1.

Figura 2: Representaci´on gr´afica de los datos de la tabla 1.

3

˜ de algoritmos
Diseno
2014 - 2015

2

Soluci´
on cuadr´
atica

La siguiente soluci´
on explora todos los segmentos posibles de la secuencia y es similar a la anterior solo que
utiliza el calculo de la suma del anterior segmento para el siguiente ahorrando uno de losbucles.

2.1

Estudio anal´ıtico

El c´
odigo del algoritmo es el siguiente:
void segSumaMaxF ( string fname ) {
vector < int > V ;
int n ,i ,j , sum , maxSum , start , end ;
leerFichero ( fname , &V , & n ) ;
maxSum = V [0]; start = 0; end = 0;
for ( i = 0; i < n ; i ++) {
sum = 0;
for ( j = i ; j < n ; j ++) {
sum = sum + V . at ( j ) ;
if ( sum > maxSum ) {
maxSum = sum ;
start = i ;
end = j...

Leer documento completo

Regístrate para leer el documento completo.