Could you tell me the algorithmic complexity of this code, in particular, how complex is the function map
numero = map(lambda x: x[0], lista)
map(lambda x: (numero.count(x)), sorted(set(numero)))
Mapping algorithm complexity
5
asked by anonymous 19.04.2016 / 20:17
2 answers
-2
Map is a part of the functional programming that you can do in Python. In it we can apply the regression algorithm in smaller code space.
In this case, in its first line, the first map takes index 0 of the variable list:
number = map (lambda x: x [0], list)
In the second line of your code, you are replicating the function contained in the variable number and counting the number of times the list item occurs [0], but the second map is being applied to the value: ))
map (lambda x: (numero.count (x)), sorted (set (numero)))
21.04.2016 / 19:44
1
Initially a map is O (n) because internally it iterates over the list, a linear operation, and also creates a new list of the same size to receive the transformations, also a linear operation, so we have O (n * 2) that in big O is considered O (n). However, as stated in the @JJoao comment, the final complexity will vary depending on the function that performs the transformation of the list (as% w / o in the case of its code), so for example if the / lambda function used to perform a constant operation the complexity would remain O (n).
As for the two lines:
lambdas , an operation O (n)), and lambda performs only the constant operation map ; lista has complexity O (n + (n log n)) (n for operation x[0] and "n log n" for operation sorted(set(numero))) ), however "n log n" predominates over "n "then we consider the two operations only as O (n log n). Now the interesting thing is that we get this list generated by set and feed the sorted with it, being that for each element of this list the sorted(set(numero)) operation will be performed. For this part we will say that the list generated by map has size numero.count(x) and that the sorted(set(numero))) list has size z , so we can say numero it performs w times the map operation, then we end up with the complexity O (z * w + (n log n)), where z * w dominates and is actually z , ufa!
19.04.2016 / 23:40