[Algoritmi] Aiuto per un esercizio
Ciao a tutti, sono alle prese con un esercizio di un corso di base di Algoritmi, sono un po' di giorni che ci penso ma non riesco a trovare una soluzione. La traccia é:
Supponiamo di avere n carte di credito {1....n} tale che due o più carte possono essere associate allo stesso conto. Supponiamo inoltre di possedere una funzione test(i,j) che restituisce TRUE se le carte i e j sono associate allo stesso conto e FAlSE in caso contrario. Determinare un algoritmo che faccia uso della funzione test O(nlogn) volte e che determini se, tra le n carte, più della metà sono associate allo stesso conto.
Ho pensato che se costruissi un grafo con nodi {1...n} in cui vi é un arco tra i e j se test(i, j)=TRUE il problema si ridurrebbe allo studio delle componenti connesse di un grafo, di cui abbiamo fatto a lezione l'algoritmo bastato sulla ricerca DFS. Non sono riuscito però a trovare un algoritmo che costruisca questo grafo utilizzando la funzione test O(nlogn) volte, ne mi sono venute altre idee più intelligenti..
Supponiamo di avere n carte di credito {1....n} tale che due o più carte possono essere associate allo stesso conto. Supponiamo inoltre di possedere una funzione test(i,j) che restituisce TRUE se le carte i e j sono associate allo stesso conto e FAlSE in caso contrario. Determinare un algoritmo che faccia uso della funzione test O(nlogn) volte e che determini se, tra le n carte, più della metà sono associate allo stesso conto.
Ho pensato che se costruissi un grafo con nodi {1...n} in cui vi é un arco tra i e j se test(i, j)=TRUE il problema si ridurrebbe allo studio delle componenti connesse di un grafo, di cui abbiamo fatto a lezione l'algoritmo bastato sulla ricerca DFS. Non sono riuscito però a trovare un algoritmo che costruisca questo grafo utilizzando la funzione test O(nlogn) volte, ne mi sono venute altre idee più intelligenti..
Risposte
Credo si possa ridurre il numero di test con delle semplici considerazioni, per esempio se test(u,v) = TRUE ma test(u,w) = FALSE non è necessario invocare test(v,w) per dire che non ci sarà un arco tra u e w. Potresti usare una una matrice di adiacenza, che ben si presta a rappresentare informazioni di questo tipo.
Ciao!
Ciao!
@probid L'uso di una matrice porta tuttavia automaticamente la complessità a \(n^2\) perché questa è la complessità per generare tale informazione.
@kekkodigrano Il problema di pensare a generare un grafo, per quanto l'idea sia valida, è lo stesso della matrice di adiacenza. Per sapere se c'è una connessione tra due elementi è necessario usare la funzione test e quindi la complessità sale facilmente a \(n^2\).
Una simile complessità la ottengo ovviamente anche facendo semplicemente tutti i test e restituendo TRUE nel caso in cui più della metà delle carte appartenga allo stesso conto. In effetti questo algoritmo fa solo \(n/2\) test nel caso migliore (tutte le prime \(n/2+1\) carte fanno parte dello steso conto) mentre nei vostri casi la complessità è sempre uguale.
La complessità mi suggerisce qualcosa come divide et impera o un albero.
@kekkodigrano Il problema di pensare a generare un grafo, per quanto l'idea sia valida, è lo stesso della matrice di adiacenza. Per sapere se c'è una connessione tra due elementi è necessario usare la funzione test e quindi la complessità sale facilmente a \(n^2\).
Una simile complessità la ottengo ovviamente anche facendo semplicemente tutti i test e restituendo TRUE nel caso in cui più della metà delle carte appartenga allo stesso conto. In effetti questo algoritmo fa solo \(n/2\) test nel caso migliore (tutte le prime \(n/2+1\) carte fanno parte dello steso conto) mentre nei vostri casi la complessità è sempre uguale.
La complessità mi suggerisce qualcosa come divide et impera o un albero.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo