Pascal - Complessità dei set

Forum - Pascal - Complessità dei set

Phi (Member)
Expert

Messaggi: 241
Iscritto: 30/12/2009

Postato alle 20:55
Giovedì, 19/04/2012

Pascal mette a disposizione un tipo di set, posso ad esempio usare:

Codice sorgente - presumibilmente Delphi

var
myset:set of byte;
[..]
Include(myset,2);
if 2 in myset then writeln('2 e'' presente');
Exclude(myset,2);

Vorrei sapere qual è la complessità computazione (nel caso pessimo) di queste operazioni. In particolare se non O(1), O(log n), O(n).

Ho pensato che potrebbero essere o tutte e 3 O(log n) oppure include O(1), in O(n) ed exclude O(n).

Il Totem (Admin)
Guru^2

Messaggi: 3635
Iscritto: 24/01/2006

Postato alle 13:54
Venerdì, 20/04/2012

Dipende dall'implementazione che ne fanno i compilatori. Su wikipedia c'è scritto che potrebbero usare una bitmask (quindi tutte le operazioni hanno complessità Theta(1)).
In Java, ad esempio, ne esiste un'implementazione che usa una hash table, che espone metodi di add, remove e contains ancora in tempo costante per strutture dati qualsiasi (ammettendo che la funzione di hash sia "perfetta" rispetto agli elementi inseriti).

Phi (Member)
Expert

Messaggi: 241
Iscritto: 30/12/2009

Postato alle 14:30
Venerdì, 20/04/2012

Grazie. Ma non penso usino hash.
C'è qualcuno che sa come sono stati implementati ?

Il Totem (Admin)
Guru^2

Messaggi: 3635
Iscritto: 24/01/2006

Postato alle 11:59
Domenica, 22/04/2012

Non ho detto che usano un hash. Ho detto che in Java si può fare così e che su wikipedia (alla voce Pascal - Set) c'è scritto che probabilmente usano una bitmask.

Phi (Member)
Expert

Messaggi: 241
Iscritto: 30/12/2009

Postato alle 15:49
Domenica, 22/04/2012

Sì sì. Ho capito, grazie