5

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)))
3
  • 1
    bigocheatsheet.com 19/04/2016 às 18:30
  • 1
    @LuizVieira, url muito cool!
    – JJoao
    19/04/2016 às 21:32
  • 1
    Sendo map uma função de ordem superior, esta análise pode complicar-se. Eu esperaria algo como map (f, lista) tender a ser O(n X) sendo ` X` a complexidade de f
    – JJoao
    19/04/2016 às 21:40

2 Respostas 2

1

Inicialmente 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:

  1. A primeira é O(n) pois é feito um map sobre lista, uma operação O(n)), e a lambda realiza apenas a operação constante x[0];
  2. A segunda é razoávelmente mais complicada de se avaliar. Começamos observando que 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!
-2

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

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .