Poderiam me dizer qual a complexidade algoritmica deste código, em especial, qual a complexidade da função map
numero = map(lambda x: x[0], lista)
map(lambda x: (numero.count(x)), sorted(set(numero)))
Stack Overflow em Português é um site de perguntas e respostas para programadores profissionais e entusiastas. Leva apenas um minuto para se inscrever.
Inscreva-se para participar desta comunidadeInicialmente um map
é O(n) pois internamente ele itera sobre a lista, uma operação linear, e também cria uma nova lista de mesmo tamanho para receber as transformações, também uma operação linear, assim temos O(n * 2) que em big O é considerado O(n). Contudo como dito no comentário do @JJoao a complexidade final vai variar conforme a função que realiza a transformação da lista (as lambdas
no caso do seu código), então por exemplo se a função/lambda utilizada realizar uma operação constante a complexidade permaneceria O(n).
Quanto as duas linhas:
map
sobre lista
, uma operação O(n)), e a lambda realiza apenas a operação constante x[0]
;sorted(set(numero)))
possui complexidade O(n + (n log n)) (n para a operação set
e "n log n" para a operação sorted
), contudo "n log n" predomina sobre "n" então consideramos as duas operações apenas como O(n log n). Agora o interessante é que pegamos essa lista gerada por sorted(set(numero))
e alimentamos o map
com ela, sendo que para cada elemento dessa lista será realizada a operação numero.count(x)
. Para essa parte vamos dizer que a lista gerada por sorted(set(numero)))
possui tamanho z
e que a lista numero
possui tamanho w
, assim podemos dizer o map
realiza z
vezes a operação numero.count
, então acabamos com a complexidade O(z * w + (n log n)), onde z * w domina sendo então na realidade O(z * w)
, ufa!Map é uma parte da programação funcional que é possível se fazer em Python. Nele nós podemos aplicar o algoritmo de regressão em menor espaço de código.
Neste caso, na sua primeira linha, o primeiro map pega o indice 0 da variável lista:
numero = map(lambda x: x[0], lista)
Na segunda linha do seu código, você está replicando a função contida na variável numero e contando o número de vezes que ocorre o item lista[0], só que o segundo map está sendo aplicado no valor: sorted(set(numero))
map(lambda x: (numero.count(x)), sorted(set(numero)))
map
uma função de ordem superior, esta análise pode complicar-se. Eu esperaria algo comomap (f, lista)
tender a serO(n X)
sendo ` X` a complexidade def