Questo è quello che ho finora:Conte occorrenza in un elenco con il tempo la complessità di O (nlogn)
alist=[1,1,1,2,2,3,4,2,2,3,2,2,1]
def icount(alist):
adic={}
for i in alist:
adic[i]=alist.count(i)
return adic
print(icount(alist))
ho fatto qualche ricerca per scoprire che la complessità temporale di list.count() è O (n), quindi, questo codice sarà O (n^2).
C'è un modo per ridurre questo a O (nlogn)?
È possibile utilizzare Counter come questo
from collections import Counter
alist=[1,1,1,2,2,3,4,2,2,3,2,2,1]
print Counter(alist)
Se si desidera utilizzare la soluzione, è possibile migliorare in questo modo
def icount(alist):
adic = {}
for i in alist:
adic[i] = adic.get(i, 0) + 1
return adic
Ancora meglio, è possibile utilizzare defaultdict come questo
from collections import defaultdict
adic = defaultdict(int)
for i in alist:
adic[i] += 1
return adic
Inoltre, si potrebbe voler considerare la complessità del tempo di v operazioni arious su diversi oggetti Python here
'get' è una funzione di un tipo di dati elenco giusto? alist.get (2,0) mi dà un errore –
@AswinMurugesh Ci scusiamo. Aggiustato. Per favore controlla ora :) – thefourtheye
Puoi spiegarmi che cosa fa esattamente? –
contatore è il vostro aiutante:
>>> from collections import Counter
>>> a = [1,2,1,3,4]
>>> Counter(a)
Counter({1: 2, 2: 1, 3: 1, 4: 1})
>>> x = Counter(a)
>>> x[1]
2
>>> x[2]
1
ottenere il conteggio di ogni elemento facilmente attraverso questo metodo
Sede [ 'collections.Counter'] (http: // docs .python.org/3/library/collections.html # collections.Counter). È lì esattamente per questo tipo di lavoro. – falsetru
Se si incrementa 'adic [i]', la complessità dovrebbe essere O (n). – Barmar
Ma come faccio a sapere la complessità del tempo? –