Equazioni di ricorrenza

[clockover]

Ciao a tutti!
Avrei bisogno di capire una cosa!
Come faccio a ricavarmi un'equazione di ricorrenza per il costo in tempo da un codice!
Non riesco proprio a capire come fare!

Ho preparato due metodi, che non hanno utilità alcuna, che però serviranno da esempio se qualcuno vuole aiutarmi!

Il metodo controllo se la somma di due interi adiacenti in un array fanno 1

Il primo metodo iterativo

public static boolean prova(int a[]){
	if(a.length == 1 || a.length == 0) return false;
	for(int i = 0; i<a.length; i++){
		if(i != a.length -1){
			if(a[i] + a[i + 1] == 1)return true;
		}
	}
	return false;
	}

Il secondo ricorsivo

public static boolean prova2(int a[]){
	if(a.length == 1 || a.length == 0) return false;
	return prova2(a, 0);
	}
private static boolean prova2(int a[], int i){
	if(i == a.length - 1)return false;
	if(a[i]  + a[i + 1] == 1)return true;
	return prova2(a, i + 1);
	}

inserisco anche il quickSort del metodo sort della classe Arrays in java se qualcuno preferisce aiutarmi con quello

private static void sort1(int x[], int off, int len) {
        // Insertion sort on smallest arrays
        if (len < 7) {
            for (int i=off; i<len+off; i++)
                for (int j=i; j>off && x[j-1]>x[j]; j--)
                    swap(x, j, j-1);
            return;
        }

        // Choose a partition element, v
        int m = off + (len >> 1);       // Small arrays, middle element
        if (len > 7) {
            int l = off;
            int n = off + len - 1;
            if (len > 40) {        // Big arrays, pseudomedian of 9
                int s = len/8;
                l = med3(x, l,     l+s, l+2*s);
                m = med3(x, m-s,   m,   m+s);
                n = med3(x, n-2*s, n-s, n);
            }
            m = med3(x, l, m, n); // Mid-size, med of 3
        }
        int v = x[m];

        // Establish Invariant: v* (<v)* (>v)* v*
        int a = off, b = a, c = off + len - 1, d = c;
        while(true) {
            while (b <= c && x[b] <= v) {
                if (x[b] == v)
                    swap(x, a++, b);
                b++;
            }
            while (c >= b && x[c] >= v) {
                if (x[c] == v)
                    swap(x, c, d--);
                c--;
            }
            if (b > c)
                break;
            swap(x, b++, c--);
        }

        // Swap partition elements back to middle
        int s, n = off + len;
        s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
        s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);

        // Recursively sort non-partition-elements
        if ((s = b-a) > 1)
            sort1(x, off, s);
        if ((s = d-c) > 1)
            sort1(x, n-s, s);
    }

    /**
     * Swaps x[a] with x[b].
     */
    private static void swap(int x[], int a, int b) {
        int t = x[a];
        x[a] = x[b];
        x[b] = t;
    }

    /**
     * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
     */
    private static void vecswap(int x[], int a, int b, int n) {
        for (int i=0; i<n; i++, a++, b++)
            swap(x, a, b);
    }

grazie in anticipo

[crick_pitomba]

Le equazioni di ricorrenza vengono utilizzate per stabilire il costo computazionale di un frammento di codice in cui vi sia la ricorsione.

Nel primo esempio che hai fatto, non c'è bisogno di utilizzare una formula di ricorrenza. come puoi verificare su un qualsiasi testo di algoritmi, il costo di un algoritmo può essere calcolato come costo di ogni singola istruzione; se ci sono cicli for basta calcolare il costo del corpo del ciclo e moltiplicarlo per il numero di volte in cui il ciclo viene ripetuto.

Prima di parlare di complessità bisogna valutare cosa si intende per complessità. Nel caso dei tuoi esempi, sono algoritmi basati sui confronti, quindi per complessità intenderemo il numero di confronti effettuati dall'algoritmo.

Bisognerebbe anche fare delle valutazioni sul comportamento dell'algoritmo sui dati e valutare se calcolare il comportamento dell'algoritmo nel caso peggiore, nel caso migliore o nel caso medio.
Alcuni algoritmi, ad esempio proprio il quicksort, hanno un comportamento particolare.
L'analisi del caso peggiore del quicksort porta ad una valutazione di una complessità dell'ordine O(n^2).
Ma analizzando i tempi medi di esecuzione, ci si accorge che l'algoritmo ha una complessità O(n log n) decisamente più favorevole.

Per questo tralascerò l'esempio del quicksort (sarebbe stato meglio un esempio basato sull'algoritmo di mergesort, più semplice da esaminare) e analizzerò i primi due algoritmi nel caso peggiore: l'array contiene n elementi e non ci sono elementi consecutivi la cui somma è 1. in questo caso l'algoritmo restituisce false solo dopo aver esaminato l'intero array.

Partiamo dalla versione non ricorsiva. In questo caso, come ho già detto, non è necessaria la formula di ricorrenza. Basta calcolare il costo, riga per riga della funzione.

Consideriamo costante il costo della chiamata a funzione che viene effettuato una volta sola

nella riga seguente abbiamo 2 confronti, che vengono eseguiti solo una volta all'inizio, quando la funzione viene chiamata

	if(a.length == 1 || a.length == 0) return false;

qui abbiamo un ciclo for, e in ogni passo del ciclo confrontiamo se i è < del numero di elementi quindi: 1 confronto ripetuto n volte

	for(int i = 0; i<a.length; i++){

nella riga successiva abbiamo di nuovo un confronto. anche in questo caso, il confronto è ripetuto n volte

		if(i != a.length -1){

ancora un altro confronto, e ancora una volta questo confronto è ripetuto n volte (in effetti potremmo valutare soltanto questa operazione come obiettivo del calcolo della complessità... ma non cambieremmo l'ordine di grandezza della complessità della funzione)

			if(a[i] + a[i + 1] == 1)return true;

il costo totale è quindi

3*n+2+c

dove c è il costo della chiamata a funzione e del return finale.
in definitiva il comportamento della funzione è lineare rispetto alla grandezza del vettore in ingresso è dunque O(n)

ripetiamo lo stesso procedimento per la funzione ricorsiva

abbiamo il costo della chiamata a funzione, che consideriamo costante [EDIT]: qui per chiamata a funzione non intendo il costo della chiamata ricorsiva ma l'insieme delle operazioni che vengono effettuate sullo stack quando c'è una chiamata a funzione!!!!

Anche in questo caso, abbiamo un confronto all'inizio della funzione

if(i == a.length - 1)return false;

poi abbiamo un nuovo confronto

	
	if(a[i]  + a[i + 1] == 1)return true;

e qui sorge il problema

	return prova2(a, i + 1);

non possiamo dire quanto costa questa chiamata, perchè il costo della funzione ricorsiva è proprio l'incognita che stiamo cercando.

Per questo, ci facciamo aiutare dalle formule di ricorrenza: definisco t[j] il costo della chiamata della funzione su j elementi.

In assoluto non so quanto valga t[j] ma posso fare delle valutazioni.

Per prima cosa osservo il costo della base della ricorsione: si ha banalmente la chiamata su un array di un solo elemento e la funzione restituisce false alla prima riga, quindi dopo il primo confronto

T[1]=O(1);



nel passo ricorsivo, su un array di n elementi posso osservare che effettuo 2 confronti e poi faccio una chiamata riducendo di 1 elemento la dimensione dell'array quindi posso sicuramente scrivere che
t[n]=2+t[n-1]

in definitiva il mio costo è definito dalla seguente equazione di ricorrenza

t[n]       =O(1)         per n=1;
           =2+t[n-1]     per n>1;

A questo punto, usando il metodo iterativo possiamo risolvere l'equazione di ricorrenza:
t[n]=2+t[n-1]

ma, applicando l'equazione di ricorrenza a t[n-1] possiamo scrivere
t[n-1]=2+t[n-2]

sostituendo
si ha
t[n]=2+t[n-1]=2+2+t[n-2]

iterando ancora
t[n]=2+t[n-1]=2+2+t[n-2]=2+2+2+t[n-3]
Osserva che il numero di volte in cui compare il valore 2 corrisponde al valore che sottraggo ad n in ogni iterazione.
quindi in generale si avrà
t[n]=i*2+t[n-i]

Ti ricordo che stiamo esaminando il caso peggiore, quindi la chiamata ricorsiva terminerà quando avremo completato l'array ovvero quando i=n-1 e in quel caso il costo della chiamata sarà quello della base della ricorsione, ovvero t[1]=O(1);
quindi sostituendo avremo
t[n]=(n-1)*2+t[n-(n-1)]=(n-1)*2+t[1]=O(n)

anche in questo caso la complessità è lineare.

spero di essere stato sufficientemente chiaro...

[clockover]

Innanzitutto grazie per la chiarezza e per la precisione della risposta! Ti rispondo solo ora perchè sono appena tornato da lavoro!

Dunque posso dire che per ricavarmi un'equazione di ricorrenza e quindi per ricavarmi il costo computazionale di un algoritmo ricorsivo devo immaginare di dare un input e vedere come lavora l'algoritmo!

L'equazione

t[n] = 2 + t[n - 1]

t[n] = costo totale (in questo caso particolare dell'array di dimensione n)
2 = costo lineare dei due confronti
t[n - 1] = in questo caso confrontiamo l'intero array meno un elemento

Ora preparo un altro pezzetto di codice e provo a risolverlo! Grazie ancora sei stato grande!

[crick_pitomba]

Originariamente inviato da clockover

Dunque posso dire che per ricavarmi un'equazione di ricorrenza e quindi per ricavarmi il costo computazionale di un algoritmo ricorsivo devo immaginare di dare un input e vedere come lavora l'algoritmo!

L'equazione

t[n] = 2 + t[n - 1]

t[n] = costo totale (in questo caso particolare dell'array di dimensione n)
2 = costo lineare dei due confronti
t[n - 1] = in questo caso confrontiamo l'intero array meno un elemento

Si, di solito il costo computazionale viene calcolato esprimendo il numero di operazioni in funzione del numero di elementi su cui le operazioni vengono effettuate, quindi devi immaginare di dare un input.

di solito
n è il numero di elementi dell'array
t[n] è il numero di operazioni che effettui

se il cuore dell'algoritmo è la ricerca il numero di operazioni corrisponde al numero di confronti, se il cuore dell'algoritmo è un prodotto tra matrici allora il numero di operazioni potrebbe essere il numero di somme e di prodotti.

Un buon esercizio potrebbe essere questo: prova a scrivere, in forma ricorsiva e non, l'algoritmo di ricerca binaria e prova a calcolarne il costo in entrambi i casi.

[clockover]

Ho scritto anche questo algoritmo per la ricerca in un Array non ordinato (poi posto anche quello di ricerca binaria) e ho provato a calcolarne i costi per poi scrivere un'equazione!

public static boolean presente(int a[], int k){
		if(a.length <= 7){
			for(int i = 0; i<a.length; i++){
				if(a[i] == k)return true;
				}
			return false;
			}
		return presente(a, k, 0, a.length - 1);
	}
	
	private static boolean presente(int a[], int k, int up, int low){
		if(up > low)return false;
		if(a[up] == k || a[low] == k)return true;
		return presente(a, k, up + 1, low - 1);
	}

Per (n <= 7)
ricerca iterativa, in questo caso il costo è dato dall'intero ciclo for ed ha ovviamente costo O(n)

Per (n > 7)
In questo caso ho tre istruzioni a costo unitario prima della chiamata ricorsiva

if(a.length <= 7)

if(up > low)return false;

if(a[up] == k || a[low] == k)return true;

dopo questa istruzione ho la mia chiamata ricorsiva

Ora qui siccome io ho una scansione dell'array in entrambi i lati posso dire l'array viene scandito in metà del tempo!

Quindi la mia equazione di ricorrenza potrebbe essere del tipo

T[n] = 3 + T[(n - 1)/2]

Ho anche provato a risolverla e chiedo venia nel caso di cappellaggini!
iterando continuamente fino all'avverarsi del caso base (poi imparerò ad essere più preciso)

T[n] = 3*(n - 1)/2 + T[1] = 
      (3*n)/2 - 3

e qui il costo asintotico dunque risulterebbe essere ancora O(n)

penso di essermi sbagliato da qualche parte..


EDIT
Ecco dove sicuramente ho sbagliato! Nel costo di 3 è inclusa anche l'istruzione del primo metodo! Che però non va contata nelle successive chiamate ricorsive! Ora provo a rifare tutto!

[clockover]

Allora!

T[n] = 1 + 2 + T[n - 2]

n - 2 perchè ad ogni chiamata ricorsiva tolgo 2

quindi succede che il passo base viene richiamato quando n - 2k = 0 quindi k = n/2

posso dire dunque che T[n] = 1 + 2*n/2 + T[1] = n + 1, dunque il costo dovrebbe venire O(n)

[clockover]

Qui provo con un algoritmo di ricerca binaria

public static boolean binSearchRic(int a[], int k){
	if(a[0] == k || a[a.length - 1] == k)return true;
	if(a[0] > k || a[a.length - 1] < k)return false;
	return binSearchRic(a, k, 0, a.length -1);
}
private static boolean binSearchRic(int a[], int k, int low, int high){
	if(low > high)return false;		
	int mid = (low+high)/2;
	if(a[mid] == k)return true;
	if(k < a[mid])return binSearchRic(a, k, low, mid - 1);
	else return binSearchRic(a, k, mid + 1, high);
}

if(a[0] == k || a[a.length - 1] == k)return true;

costo unitario

if(a[0] > k || a[a.length - 1] < k)return false;

costo unitario

if(low > high)return false;		
int mid = (low+high)/2;
if(a[mid] == k)return true;

tre chiamate a costo unitario

if(k < a[mid])return binSearchRic(a, k, low, mid - 1);

chiamata ricorsiva

dunque.....

T[n] = 2 + 3 + T[n/2 - 1]

in questo caso la scrittura T[n/2 - 1] dovrebbe andare bene dato che ad ogni chiamata dimezzo sempre l'array!
Come posso calcolare questa equazione? Ma innanzi tutto.... è stato corretto il mio ragionamento?

[GiudaConHerpes]

Sottoscrivo questa interessante discussione.

Baci,
Giuda

P.S.
@crick_pitomba: puoi dirci qualcosa sul metodo dell'albero di ricorsione?

[crick_pitomba]

dunque...

per quanto riguarda la ricerca in un array non ordinato (post 5 e 6) effettivamente il tempo di ricerca è lineare: devi per forza esaminare tutti gli elementi nel caso peggiore
l'equazione di ricorrenza

T[n] = 1 + 2 + T[n - 2]

è corretta e la sua soluzione è effettivamente O(n)


passiamo alla ricerca binaria

hai impostato correttamente l'equazione

per risolverla possiamo usare ancora il metodo iterativo.

per comodità scriviamo l'equazione in questo modo

T[n]=c + T[n/2] (a)

Trascuriamo quel "-1" all'interno dell'argomento della T. Tale valore, non incide più di tanto nella soluzione dell'equazione. La sua presenza deriva da un'ottimizzazione dell'algoritmo.si potrebbe dimostrare che se modificassimo l'algoritmo eliminando questa ottimizzazione il suo costo resterebbe sempre logaritmico.

Allo stesso modo ho indicato con c l'insieme dei passaggi costanti che devo fare ad ogni chiamata della funzione

Per utilizzare il metodo iterativo, dobbiamo calcolare il valore di T[n/2] e sostituirlo nell'equazione

Ti faccio un esempio numerico per farti capire come funziona. consideriamo n=4

T[4]=c+ T[4/2]=O(1)+T[2]


quindi nel caso in cui voglia calcolare T[n/2], ho
T[n/2]=c+ T[(n/2)/2]=c+T[n/4]=c+T[n/(2^2)]

nota che ho espresso n/4 come n su 2 al quadrato... il motivo per cui ho fatto questa scelta sarà chiaro nei prossimi passaggi

sostituendo nella equazione (a) si ha
T[n]=c + c+T[n/(2^2)] (b)

ripetiamo ancora una volta il procedimento
T[n/4]=c+T[(n/4/2]=c+T[n/8]=c+T[n/(2^3)]
anche in questo caso ho espresso 8 come 2^3


sostituendo nella equazione (b) si ha

T[n]=c + c+c+T[n/(2^3)] (c)


ora ne abbiamo abbastanza per capire il termine generico come è fatto.

osserviamo infatti che ci sono 3 termini c e l'esponente del 2 è proprio 3

dunque il termine generico sarà
t[n]=i*c+T[n/(2^i)]

quando raggiungerò la base della ricorsione?
quando dovrò lavorare su un array di 1 solo elemento

quindi quando n/(2^i)=1....
i=log n (in base 2)
in definitiva
t[n]=c*(log n) +T[1]= O(log n)

in casi come questi ed altri sicuramente più complessi, risolvere le equazioni di ricorrenza con il metodo iterativo potrebbe risultare poco intuitivo...

Alcune persone trovano utile rappresentare graficamente le iterazioni della ricorrenza, si ottiene così l'albero di ricorsione.

L'albero di ricorsione viene costruito in questo modo. Nella radice dell'albero si inseriscono i termini dell'equazione di ricorrenza che non rappresentano la chiamata ricorsiva (in pratica i termini che non hanno la forma T[...])

Nel nostro caso abbiamo solo il termine c

	C

come foglie della radice introduciamo i termini che dipendono dalla T

	C
       / 
    T[n/2]

se avessimo avuto un'equazione di ricorrenza del tipo

T[n]=T[n/2]+T[n/2]+n+c

avremmo rappresentato l'albero in questo modo

          n+C
          / \
    T[n/2]   T[n/2]

a questo punto espandiamo ogni foglia dell'albero

	c
       / 
      c
     / 
  T[n/4]

iteriamo ancora una volta

          c
         / 
        c
       / 
      c
     / 
  T[n/8]

Dall'andamento dell'argomento della T[], si evince che l'altezza dell'albero è log n.

Calcolo dunque il costo di ogni riga dell'albero

       albero        costo della riga
          c		 c
         / 
        c               c
       / 
      c                 c
     / 
  ...

in definitiva ho (log n) righe di costo c
Pertanto l'algoritmo ha costo c*log n=O(log n)

In questo caso particolare, non ci sono vantaggi evidenti nell'uso dell'albero di ricorsione, ma in caso di equazioni di ricorrenza più intricate, ad esempio
t[n]=t[n/8]+t[3/4n]+n

l'albero di ricorsione potrebbe essere utile per intuire in modo più semplice qual è la base della ricorrenza e calcolarne la soluzione.

[clockover]

Grazie mille sei stato davvero decisivo per farmi capire queste cose! Proverò a postare qualcosa più in la e se potrai gli darai uno sguardo per farmi capire se sono sulla giusta strada... il mio esame si avvicina!

[crick_pitomba]

mi fa piacere...


in bocca al lupo

[clockover]

Sono costretto a disturbare di nuovo!

static long prodotto(long m, long n){
    if((m == 0 || n == 0)) return 0;
    if(n == 1) return m;
    return m + prodotto(m, n - 1);
    }

static long potenza(long x, long y){
    if(y == 0) return 1;
    return prodotto(x, potenza(x, y - 1));
    }

Anche se si vede a occhio il costo computazionale del primo metodo seguo il metodo più rigoroso dell'equazione di ricorrenza

quindi

T[1] = c

a causa dell'unica istruzione che viene eseguita (a dirla tutta sono 2)
mentre per una dimensione generica "n"

T[n] = O(1) + T[n - 1]

che mi porta ovviamente a O(n)

ora se volessi calcolarmi il costo computazionale del metodo potenza?
vorrei provarci ma...

T[0] = c (quindi il passo base costo costante)
T[1] = c + T[1 - 1] + ....
e dunque anche 
T[n] = c + T[n - 1] + ....

questo metodo potenza (ovviamente serve solo a scopi didattici perchè esistono metodi molto migliori per calcolarsi il fattoriale) richiama ricorsivamente se stesso n volte, n perchè il caso base è quando è uguale a 0! Non riesco a impostarmi l'equazione!
Se invece usassi un albero di ricorsione sarebbe più semplice la cosa?
Grazie ancora per l'attenzione!

[crick_pitomba]

Vediamo se riesco a darti una mano...

Come il costo di un ciclo for è il costo del nucleo del ciclo moltiplicato n volte, il costo di una chiamata a funzione è il costo del nucleo della chiamata a funzione. il fatto che la funzione chiamata sia a sua volta ricorsiva, non ha importanza. Ormai il suo costo l'hai calcolato

Il costo di "prodotto" è O(valore del secondo argomento della chiamata a funzione)

il costo di prodotto (x,n) è n.

Di potenza non conosci il costo computazionale ma conosci il valore dell'output.
L'output di potenza (x,n) è x^n;


Edit[corretto un errore nell'equazione...]

quindi
il costo di prodotto(x,potenza(x,n-1))
è il valore del secondo argomento della funzione ovvero è il costo dell'output di "potenza (x,n-1)" al quale va sommato il costo della chiamata ricorsiva
ovvero O(x^(n-1))



quindi la chiamata ricorsiva ha il costo
T[n]=(x^(n-1))+T[n-1]+c
t[n-1] è il costo della chiamata alla funzione potenza che vogliamo calcolare
x^(n-1) è il contributo della funzione prodotto il cui costo è dato dall'output della funzione potenza

Iterando
T[n]=(x^(n-1))+(x^(n-2)+T[n-2]+c)+c=
x^(n-1)+c+(x^(n-2)+T[n-2]+c+c

T[n]=x^(n-1)+x^(n-2)+(x^(n-3)+T[n-3]+c+c+c

T[n]=x^(n-1)+x^(n-2)+...+x^(n-i+1)+c+(x^(n-i)+T[n-i]+c+c+c+c
T[n]=x^(n-1)*c+x^(n-2)*c+...+x^(1)+T[1]+c*n

in definitiva il costo è un polinomio di grado n-1;

è interessante osservare come la scelta dell'ordine degli argomenti della funzione prodotto sia importante.

Ovviamente tu hai scritto il codice per fare qualche test, ma intuitivamente si capisce che per come hai scritto il codice che si potrebbe fare di meglio.
Ora ti mostro come possiamo usare in pratica le equazioni di ricorrenza e a cosa serve in pratica il costo computazionale

Osserva questa cosa

return prodotto(x, potenza(x, y - 1));

per come hai scritto il codice della funzione prodotto
visto che potenza (x,y-1) è maggiore di x
chiami molte volte la funzione prodotto su un numero piccolo: sommi x^(y-1) volte il piccolo numero x

Scrivendo la funzione in questo modo
return prodotto(potenza(x, y - 1),x);
chiameresti poche volte la funzione prodotto su un numero grande: sommi x volte il grande numero x^(y-1)

in questo caso la funzione di ricorrenza diventa
T[n]=x+T[n-1]+c
Iterando
T[n]=x+T[n-1]+c=x+c+x+T[n-2]=x+c+x+c+x+T[n-3]=
=(i-1)*x+(i-1)*c+T[n-i]=(n-1)*(x+c)+T[1]

la funzione è sempre polinomiale
ma mentre prima era un polinomio di grado n, adesso è un polinomio di grado 1 con un coefficiente che dipende da n.

E' ovvio che c'è una bella differenza tra i due metodi. Ad esempio, per calcolare 5^5 con la funzione scritta nel secondo modo faresti una ventina di chiamate della funzione prodotto, mentre con la funzione scritta nel primo modo circa 780.

niente male per aver cambiato solo l'ordine di due elementi...

P.s. l'albero di ricorsione non avrebbe cambiato di molto il discorso... è solo un modo per rappresentare graficamente i conti!

[clockover]

Questo è un esercizio d'esame del primo appello

public static boolean mistero1(int a[], int b[]){
    if(a.length > b.length) return false;
    return mistero1(0, a, b);    
}
public static boolean mistero1(int k, int a[], int b[]){
    if(k == a.length) return true;
    return mistero2(a[k], b, 0, b.length - 1) && mistero1(k + 1, a, b);
}
public static boolean mistero2(int x, int b[], int l1, int l2){
    if(l1 > l2) return false;
    int c = (l1 + l2)/2;
    if(x == b[c]) return true;
    if(x < b[c]) return mistero2(x, b, l1, c -1);
    return mistero2(x, b, c + 1, l2);
}

allora a primo acchitto cerco di capire quello che fa il nostro programmino!
Da quello che mi sembra di aver capito è un confronto tra due array, ma almeno l'array b deve essere ordinato perchè sfrutta il metodo di ricerca dicotomica!

Posso cominciare un pezzo alla volta
parto da mistero2(x, b[], l1, l2)
già abbiamo parlato di questo metodo e il suo costo è O(logn) per via della nostra equazione di ricorrenza

T[n] = c + T[n/2]

iterandola diventerebbe

T[n] = logn*c + T[1]

e dunque il costo sarebbe O(logn)

ora prendiamo il metodo mistero1(k, a[], b[])
chiamiamo con "h" la dimensione dell'array a[]

andando a controllare la nostra chiamata ricorsiva scopriamo che il numero di volte che viene chiamato il metodo dipende dalla dimensione di a, e dunque "h"! Facendo un'analisi dovremmo avere un risultato del genere

T[h] = c + O(logn) + T[h - 1]

iterando più volte il risultato dovrebbe essere del tipo

c + O(logn) + c + O(logn) + T[h - 2]

abbiamo dunque elementi sufficienti per capire come procederà cioè in

T[h] = h*(c + O(logn)) + T[1]

e dunque nel caso peggiore, cioè quando abbiamo due array perfettamente uguali, il costo complessivo sarà

O(h*logn)

spero di non aver detto stupidaggini

grazie ancora

[crick_pitomba]

Scusa il ritardo ma ho cambiato i pezzi del pc ed ho qualche problema...

non hai detto stupidaggini

ad occhio mi sembra che l'algoritmo verifichi che tutti gli elementi dell'array a siano presenti in b. quindi il costo deve essere dato dal prodotto fra la dimensione di a e il costo della ricerca in b.

E infatti come hai dimostrato il costo è proprio quello... bravo!!!

[clockover]

Non ti preoccupare ormai ho capito che sto parlando con una persona corretta! Grazie ancora