Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - complessità computazionale
Forum - C/C++ - complessità computazionale

Avatar
belledetta (Normal User)
Rookie


Messaggi: 25
Iscritto: 07/09/2010

Segnala al moderatore
Postato alle 11:58
Domenica, 15/05/2011
ciao ho svolto un programmino che genera un vettore di numeri casuali(con ripetizioni), poi una volta inserito un valore x cerca tutte le possibili coppie di valori presenti nel vettore che diano come somma x.
Se ho fatto bene i miei conti la complessità dovrebbe essere di circa O(n^2), è possibile ottimizzare il programma?

Ho provato a ottimizzare l'algoritmo in questo modo e spero che il ragionamento sia corretto:
1) ordino il vettore con merge sort) ->o(nlogn)
2) cerco le posizione dell'elemento x nel vettore (chiamiamo j la posizione) con la ricerca dicotomica-> o(logn)
3) cerco le posizione dell'elemento x/2(se esiste altrim in numero strettam minore)(posizione k) -> o(log(n/2))
3) effettuo i confronti sommando gli elementi con posizione da 1a k e gli elementi da k+1 a j -> caso peggiore: n^2/4, caso migliore: o(1)

di fatto non ho ottimizzato nulla!!! qualcuno sa aiutarmi???

Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. #define N 1000
  6. int main()
  7. {
  8.     long long int v[N]={0};
  9.     int i=0;        //variabile decisionale per il riempimento
  10.     int n=0;        //dimensione vettore
  11.     int x=0;        // valore da cercare
  12.     int yes=0;      //flag per sapere se è stato trovata almeno una coppia
  13.  
  14.     /************************************************************************
  15.     *           RIEMPIMENTO VETTORE                 *
  16.     ************************************************************************/
  17.     printf("Inserisci dimensione del vettore\n");
  18.     scanf("%d",&n);
  19.     printf("digita:\t1 per inserimento da input\t2 per inserimento automatico casuale\n");
  20.     scanf("%d",&i);
  21.  
  22.     srand(time(NULL));
  23.  
  24.     if (i==1)   for (int j=0; j<n; j++)  scanf("%d",&v[j]);  //inserimento manuale
  25.     else        for (int j=0; j<n; j++)   v[j]=rand();       //inserimento automatico
  26.  
  27.     for( int j=0; j<n; j++)   printf("v[%d] = %d\n",j+1,v[j]);   //stampa vettore
  28.  
  29.     /************************************************************************
  30.     *               RICERCA                 *
  31.     ************************************************************************/
  32.     printf("\ninserisci un valore compreso tra 0 e %d\n",RAND_MAX);
  33.     scanf("%d",&x);
  34.  
  35.     for(int j=0; j<n; j++)
  36.         for(int k=j+1; k<n; k++)
  37.             if(v[j]+v[k]==x) {printf("\nv[%d]+ v[%d] = %d + %d = %d \n",j+1,k+1,v[j],v[k],x); yes=1;}
  38.  
  39.     if(yes==0) printf("\n non ci sono valori nel vettore la cui somma sia uguale e %d\n",x);
  40.  
  41.     return 0;
  42. }


PM
Avatar
Il Totem (Admin)
Guru^2


Messaggi: 3635
Iscritto: 24/01/2006

Up
3
Down
V
Segnala al moderatore
Postato alle 12:32
Domenica, 15/05/2011
Questo è un caso particolarissimo del problema del sottoinsieme somma (che è np-completo), dove la somma che vuoi ottenere è x e il sottoinsieme ha sempre cardinalità 2.

Dal momento che devi comunque sempre trovare una combinazione di due elementi, non potrai fare a meno di avere complessità n^2. Potrai al massimo diminuire il numero di iterazioni del caso pessimo di un fattore costante, ma n^2 rimane.

Se parti col merge sort potresti testare solo i primi k elementi minori di x/2 con i successivi h elementi maggiori di x/2 e minori di x. In questo modo scarti alcune combinazioni inutili. Infatti con il tuo algoritmo nel caso pessimo fai un numero di passi pari alla sommatoria di 1, 2, 3, ..., k+h-1, ossia (k+h-1)*(k+h-2)/2, quindi (k^2+2hk-3k+h^2-3h+2)/2; con questo ne fai solo kh. In breve questo approccio è più veloce per ogni h o k tali che la loro somma sia circa maggiore di 6, ossia per tutti i casi sensati per un'elaborazione.

Ultima modifica effettuata da Il Totem il 15/05/2011 alle 13:09
ciao.... scusami ma siccome sono alle prime armi cn questo linguaggio non sono riuscita a seguire tutto quello che hai scritto o per lo meno dal terzo paragrafo in poi. - belledetta - 15/05/11 17:04
Tu testi un elemento con tutti i successivi: questo ti richiede un certo numero di passi inutili (infatti la somma di due numeri entrambi minori o maggiori di x/2 non può essere x). La mia idea è di testare solo gli elementi minori di x/2 con quelli maggiori di x/2. - Il Totem - 16/05/11 13:40
si hai ragione infatti ho pensato dopo di fare come hai detto tu, in ogni caso la complessità è polinomiale...nel commento al post successivo ho scritto in che modo ho risolto il problema - belledetta - 18/05/11 09:48


"Infelici sono quelli che hanno tanto cervello da vedere la loro stupidità."
(Fligende Blatter)

"Dubitare di se stessi è il primo segno d'intelligenza."
(Ugo Ojetti)
PM
Avatar
Ultimo (Member)
Expert


Messaggi: 513
Iscritto: 22/05/2010

Up
1
Down
V
Segnala al moderatore
Postato alle 17:49
Domenica, 15/05/2011

Se il vettore o Array da testare verrà caricato con un numero abbastanza
elevato di elementi numerici, con un ordinamento del vettore tramite
QuickSort o MergeSort, potresti andare ad eslcudere gli elementi nel
vettore che sono uguali e maggiori del valore x, in modo da ridurre
il numero di iterazioni e confronti/somme da effettuare, in seconda fase
inizierai l'iterazione dal primo valore utile nel vettore verso il valore minimo
in modo tale che quando la somma tra i due elementi risulterà inferiore
al valore x, salterai i restanti valori da iterare, insomma più o meno,
lo scopo è quello di ridurre il numero di iterazioni e di somme.

ok. ora ho risolto il problema...posso prima ordinare il vettore con mergesort con O(nlogn), poi dato x, per ogni v[j] del vettore cerco x-v[j]) nel vettore con la ricerca binaria, avrò quindi O(nlogn). In definitiva in questo modo ho complessità totale pari a o(nlog) ed è ottima. - belledetta - 18/05/11 09:46


Ultimo (Hai voluto la bicicletta ? ....)

Studiare LINQ, WPF, ASP.NET MVC, Entity Framwork, C#, Blend, XAML, Javascript, HTML5, CSS .....(tanta roba)

https://www.dropbox.com/s/c2aots5x4urgbhf/setup_game_sudoku ...
PM