Programación Java

Programació 1. Exercicis d’eficiència
1.Un algorisme triga 5 segons a resoldre un problema de grandària n=128. Quant trigarà a resoldre un
problema de grandària256,
a)si el cost de l'algorisme és constant?
b)si el cost de l’algorisme és lineal?
c)si el cost de l’algorisme és cúbic?
d)si el cost de l'algorisme ésquasilineal?
e)si el cost de l'algorisme és exponencial O(10n)?

2.Hem provat un algorisme A amb n dades i triga n3 minuts a resoldre un problema. Un altre algorisme Bresol el mateix problema i amb les mateixes n dades triga n4 segons. Amb quin dels dos us quedaríeu (tenint
en compte que el tamany de les dades d’entrada no serà sempreel mateix)?
3.Compara l’eficiència d’aquests dos algorismes que serveixen per insertar un element en una taula
ordenada, mantenint l’ordre.
2

7

10

1519

23

8
Versió 1:

recórrer la taula fins trobar la posició, i, on ha d’anar l’element
moure els valors, des de i fins al final, un lloc enrera
posar elnou valor a la posició i

Versió 2:

posar el nou valor a la primera posició buida
ordenar el vector (el millor algorisme d’ordenació té cost O(nlogn))

4.Esdemana calcular l’eficiència del següent algorisme (suposarem que sempre la constant MAX és més
gran que el valor que es demana per teclat). Cal indicar el cost de cadainstrucció, així com el cost total del
programa aplicant les regles de estudiades. Un cop sapigueu l’ordre de complexitat, intenteu esbrinar què fa
el programa idissenyeu un altre algorisme que sigui més eficient.
acció Ordenar (V1:taula[] enter; V2: taula[] enter; num: enter) és
var
posmax,aux:enter;
inici
per (i=0; i