[Algoritmi] Aiuto per un esercizio

[kekkodigrano]

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

[probid]

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!

[apatriarca]

@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.