[Algoritmi] costo funzione complessa.

[wota]

Sia due funzioni :


static int[] M1(int n) {
///////////////////
}

static double M2(int[] a) {
//////////////////
}

ove il codice non ha importanza perché vorrei capire il concetto generale, quindi assumiamo per esempio che M1 abbia un costo teta(2^z) ove z è la dimensione dell'input dell'intero ossia il numero di bit. Per M2 il costo asintotico della funzione assumiamo sia teta(w) ove w è la sua dimensione dell'input, ossia il numero di elementi dell'array.

In un esercizio mi chiedeva:
Determinare il costo asintotico dell’algoritmo descritto da M in funzione di z, dimensione dell’input. In particolare, evidenziare le componenti di costo dovute a M1 e quelle dovute a M2.

ove la funzione M è:

static double M(int n) {
return M2(M1(n));
}

Non riesco a capire come si dovrebbe eseguire il costo in questo caso dato che poi le dimensioni dell'input non sono le stesse

[apatriarca]

Invece il codice ha importanza.. Qual'è la dimensione del vettore in output da M1?

[wota]

static int[] M1(int n) {

int[] p = new int[n];
for(int i=0; i < n; i++) p[i]=i+1;
return p;

}

static double M2(int[] a) {

double t = 0;
double[] temp = new double[a.length-1];
for(int i = 0; i < temp.length; i++)
temp[i] = (a[i] + a[i+1])/2.0;

for(int i = 1; i < temp.length/2; i++)
t += Math.sqrt(temp[temp.length-i]-temp[i-1]); // assumere Theta(1)

return t;

}

n

[apatriarca]

\(M2(M1(n))\) è del tutto equivalente a prima calcolare \(a = M1(n)\) e poi calcolare \(M2(a).\) Il costo totale è quindi semplicemente la somma delle due complessità. La parte più complicata è legare tutto all'input di \(m1\). Ma se prendiamo \(b\) il numero di bit di \(n\) abbiamo che la complessità di \(M1\) è \(\Theta(2^b)\) e quella di \(M2\) è \(\Theta(n) = \Theta(2^b).\) Per cui alla fine hai che la complessità è \(\Theta(2^b) = \Theta(n)\).