C/C++ - complessità computazionale

Forum - C/C++ - complessità computazionale

belledetta (Normal User)
Rookie

Messaggi: 25
Iscritto: 07/09/2010

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++

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define N 1000
int main()
{
    long long int v[N]={0};
    int i=0;        //variabile decisionale per il riempimento
    int n=0;        //dimensione vettore
    int x=0;        // valore da cercare
    int yes=0;      //flag per sapere se è stato trovata almeno una coppia
 
    /************************************************************************
    *           RIEMPIMENTO VETTORE                 *
    ************************************************************************/
    printf("Inserisci dimensione del vettore\n");
    scanf("%d",&n);
    printf("digita:\t1 per inserimento da input\t2 per inserimento automatico casuale\n");
    scanf("%d",&i);
 
    srand(time(NULL));
 
    if (i==1)   for (int j=0; j<n; j++)  scanf("%d",&v[j]);  //inserimento manuale
    else        for (int j=0; j<n; j++)   v[j]=rand();       //inserimento automatico
 
    for( int j=0; j<n; j++)   printf("v[%d] = %d\n",j+1,v[j]);   //stampa vettore
 
    /************************************************************************
    *               RICERCA                 *
    ************************************************************************/
    printf("\ninserisci un valore compreso tra 0 e %d\n",RAND_MAX);
    scanf("%d",&x);
 
    for(int j=0; j<n; j++)
        for(int k=j+1; k<n; k++)
            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;}
 
    if(yes==0) printf("\n non ci sono valori nel vettore la cui somma sia uguale e %d\n",x);
 
    return 0;
}

Il Totem (Admin)
Guru^2

Messaggi: 3635
Iscritto: 24/01/2006

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

Ultimo (Member)
Guru

Messaggi: 877
Iscritto: 22/05/2010

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

If ok Then GOTO Avanza else GOTO Inizia