In Python è possibile ottenere l'intersezione di due insiemi fare:Intersezione complessità
>>> s1 = {1, 2, 3, 4, 5, 6, 7, 8, 9}
>>> s2 = {0, 3, 5, 6, 10}
>>> s1 & s2
set([3, 5, 6])
>>> s1.intersection(s2)
set([3, 5, 6])
Chiunque conosce la complessità di questo incrocio (&) algoritmo?
MODIFICA: Inoltre, qualcuno sa qual è la struttura dati dietro un set Python?
La risposta sembra essere a search engine query away. Puoi anche usare questo direct link to the Time Complexity page at python.org. Riepilogo:
Average: O(min(len(s), len(t))
Worst case: O(len(s) * len(t))
MODIFICA: come indicato da Raymond di seguito, non è probabile che si verifichi lo scenario "worst case". L'ho incluso originariamente per essere completo, e lo lascio per fornire il contesto per la discussione qui sotto, ma penso che Raymond abbia ragione.
Il intersection algorithm viene sempre eseguito su O (min (len (s1), len (s2))).
in puro Python, sembra che questo:
def intersection(self, other):
if len(self) <= len(other):
little, big = self, other
else:
little, big = other, self
result = set()
for elem in little:
if elem in big:
result.add(elem)
return result
[Risposta alla domanda in fase di montaggio aggiuntivo] La struttura dei dati dietro insiemi è una hash table.
non ** sempre **, controlla: http://wiki.python.org/moin/TimeComplexity#set – juliomalegria
Secondo la wiki che ho linkato sopra, il caso peggiore per 'elem in big' nel tuo codice è O (n) (anche se la media è ovviamente O (1)). Questa è la base per il caso peggiore di intersezione di O (len (s) * len (t)). Qualche idea del perché? –
Il "caso peggiore" presuppone dati inappropriati per l'uso nella tabella hash utilizzata da * dict * e * set *.I dati dovrebbero essere qualcosa di simile che ogni dato avesse esattamente lo stesso valore di hash - questo costringerebbe la tabella hash a fare qualcosa di simile a una ricerca lineare per fare il controllo \ _ \ _ contiene \ _ \ _. IOW, non mi preoccuperei affatto di questo. L'intersezione impostata è ciecamente veloce: riutilizza persino i valori di hash memorizzati internamente, quindi non è necessario effettuare chiamate a * hash() *. –
Set intersezione di due insiemi di dimensioni m,n può essere realizzato con O(max{m,n} * log(min{m,n})) nel seguente modo: assumere m << n
1. Represent the two sets as list/array(something sortable)
2. Sort the **smaller** list/array (cost: m*logm)
3. Do until all elements in the bigger list has been checked:
3.1 Sort the next **m** items on the bigger list(cost: m*logm)
3.2 With a single pass compare the smaller list and the m items you just sorted and take the ones that appear in both of them(cost: m)
4. Return the new set
Il ciclo nella fase 3 avrà una durata di n/m iterazioni e ogni iterazione prenderà O(m*logm), così Avrai la complessità del tempo di O(nlogm) per m < < n.
Penso che sia il limite inferiore migliore esistente
che è un brutto caso peggiore, non è vero? – juliomalegria
Anch'io ne sono rimasto sorpreso! Forse è un problema di avere diversi tipi di dati mescolati nei due set che sono intersecati? –
Non sembra che usi prima un ordinamento (che * richiede che gli oggetti abbiano un ordinamento *), ma piuttosto fa un "hash probe": forse per un migliore 'C' e medio (e * nessun requisito di ordinamento *). La massima complessità richiesta, AFAIK, è circa 'O (n log n) + O (n)', con un ordinamento. Tuttavia, Big-O è un limite superiore e ci sono considerazioni pratiche quindi ... –