Complessità algoritmo

[claudiocarcaci]

Ciao a tutti, ho ideato un algoritmo di "copertura intelligente" di combinazioni secondo le informazioni apportate da tali combinazioni. Vabè non è importante questo aspetto visto che è un po' contorto spiegarlo e non è l'oggetto della domanda.

Come tutti gli algoritmi di copertura funziona a "passate", in particolare ho:

alcune istruzioni che costruiscono A e B iniziali t.c.: |A| = n, |B| = n
while(passata nesima)
{
 for i in A
 {
  for j in B
  {
   istruzioni
  }
 }
 C = alcuni elementi di A t.c. |C|=ln(|B|)
 aggiorna A: A=C
 aggiorna B: B=A u B
}

Chiaramente si ha che i due for innestati hanno complessità |A|*|B|.
La prima passata si ha che costa $ O(n^2) $ e impone $ |A|=ln(n) $ mentre $ |B|=n+n=2n $
La seconda passata costa $ O(2n*ln(n)) $ e impone $ |A|=ln(ln(n)) $ mentre $ |B|=2*n+ln(n) $
La terza passara costa $ O((2*n+ln(n))*ln(ln(n))) $ e impone $ |A|=ln(ln(ln(n))) $ mentre $ |B|=2*n+ln(n)+ln(ln(n)) $

E così via finchè ovviamente $ |A|=0 $

Questo da luogo ad una complessità per le prime quattro iterazioni pari a:
$ O(n^2+2*n*ln(n)+(2*n+ln(n))*ln(n)+(2*n+ln(n))*ln(ln(n))) $

La parte ingestibile di tutto questo è $ ln(ln(ln(...ln(n)...)) $
E' possibile trasformarlo in qualcosa di "confrontabile" in modo da ricavare analiticamente la soluzione?
La complessità dell'algoritmo pare essere $ O(n^2+n*ln(n)) $ ma è una stima per difetto e non fa molto bene anche se da test empirici risulta proprio convergere a quel valore poichè ci sono condizioni molto forti di stop che fanno sì che alla terza passata l'algoritmo concluda le sue operazioni.

[hamming_burst]

mmm simpatico algoritmo...

Direi che la prima passata con $|A|=|B|=n$ è meglio tenerla come se fosse una iterazione separata. Questo perchè $A$ subito dopo diviene funzione della cardinalità di $B$ perciò non ci sarebbe più questa diversificazione di dimensione.
Direi che dalla seconda passata si può astrarre. Perciò perchè poni $|B|=n+n=2n$? se $A$ è aggiornato a C sarà $log(n) + n$.
Comunque in questo caso è meglio che ragioni per ricorsione, quindi formalizzare un'equazione di ricorrenza.

Premetto che considero $B=A uu B$ come $A=C$ perciò utilizzi l'$A$ aggiornato. Se questo non è vero perciò $A$ è quello originale cambiamo...

A partire dalla seconda passata si sa che $|A|=log(|B|)$ e $|B| = log(|B|) + |B|$
ponendo $|B|=n$: $|A|=log(n)$ $|B| = log(n) + n$
questa è la situazione dopo la prima passata.

Ora il cicli for compiranno: $log(n)*(log(n)+n)$
e si aggiornerà: $|A|=log((log(n)+n))$ $|B| = log((log(n)+n)) + (log(n)+n)$

ora si noterà che questa è una ricorrenza con fattore di ricorsione $T(log(n) + n)$ e complessità della funzione libera $log(n)*(log(n)+n)$
Perciò la ricorrenza sarà: $T(log(n) + n) + log(n)*(log(n)+n)$ if $n>0$

ora non ho molta voglia di calcolarla in modo preciso, prova te, perchè non è bella come ricorrenza e ci vuole qualche trucco (direi sostituzione di variabile).

ma secondo me la complessità non è lontana da quella che hai trovato cioè $O(nlogn)$ (sommando poi la prima passata), potresti subito provare a dimostrarlo per inductione se vuoi


PS: posso chiederti di che argomento è la "copertura intelligente"? (data mining?).

[claudiocarcaci]

E' un algoritmo per classificare testi... un ambito cugino del data mining

[claudiocarcaci]

In effetti c'è un errore... nel riportare ho scambiato le due istruzioni
Chiedo venia -.-''

alcune istruzioni che costruiscono A e B iniziali t.c.: |A| = n, |B| = n
while(passata nesima)
{
for i in A
{
  for j in B
  {
   istruzioni
  }
}
C = alcuni elementi di A t.c. |C|=ln(|B|)
aggiorna B: B=A u B
aggiorna A: A=C

[hamming_burst]

ok mi sembrava ci fosse qualcosa di strano, perciò ricorsivamente verrebbe così:

alg(int A, int B){

if B=0 || A=0 //condizioni da rivedere...
return 

for i in A
{
  for j in B
  {
   istruzioni
  }

alg(log(B),A+B)
}

chiamato con

alg(n,n)

facendo qualche iterazione:

n*n
A = n
B = n
B'= n + n = 2n
C = log(n)

log(n)*2n
A = log(n)
B = 2n
B'= log(n) + 2n
C= log(2n)


log(2n)*(log(n) + 2n)
A = log(2n)
B = log(n) + 2n
B'= log(2n) + (log(n) + 2n)
C= log(log(n) + 2n)

log(log(n) + 2n)*(log(2n) + (log(n) + 2n))
...

non mi tornano alcuni tuoi passaggi, ma vabbè ci ragiono domani...

[claudiocarcaci]

Ieri sera ho fatto alcuni calcoli e ho scoperto perchè non mi tornavano alcune cose:
1. la prima era: quante iterazioni fa il while esterno? In teoria ne fa al massimo n, in pratica ne farà si e no il 10%, ma come valore di riferimento prendo n che è sicuro.
2. qual è la vera grandezza di C? Qui è un dilemma visto che si ottiene combinando A e B, con le dovute simulazioni sono arrivato alla conclusione che $ C=ln(A) $

Quindi:

alcune istruzioni che costruiscono A e B iniziali t.c.: |A| = n, |B| = n
while(flag and i=1...n)
{
for i in A
{
  for j in B
  {
   istruzioni
  }
}
aggiorna B: B=A u B
C = alcuni elementi di A t.c. |C|=ln(|A|)
aggiorna A: A=C

Quindi si trova con uno studio ricorsivo:
$ A(0)=n $
$ B(0)=n $
$ B(i)=B(i-1)+A(i-1) $
$ A(i)=ln(A(i-1)) $

La complessità al passo i-esimo con $ i>2 $ sarà:
$ O(A(i-1)*B(i-1))=O(ln(A(i-2))*(B(i-2)+A(i-2))= $
$ =O(ln(ln(A(i-3)))*(B(i-3)+A(i-3)+ln(A(i-3)))) $

Considerando una maggiorazione sui fattori:
$ ln(ln(A(i-3))) < ln(n) $
$ B(i-3)+A(i-3)+ln(A(i-3)) < n^2 $

La complessità di un generico passo n>2 sarà:
$ O(n^2*ln(n)) $

I passi totali saranno al massimo n, quindi la complessità globale sarà:
$ O(n+n^2+n*n^2*ln(n))=O(n+n^2+n^3*ln(n))=O(n^3*ln(n)) $

Che è una stima fortemente per eccesso ma questo è dimostrato solo da statistiche empiriche (sarebbe bello fare un test di tipo MonteCarlo).
Tuttavia considerando che costruire gli insiemi di copertura su n elementi di classe r=1...n costa:
$ O(2^n-1) $
c'è da metterci la firma!