HELP - Calculating the complexity of my algorithm. - Printable Version +- Python Forum (https://python-forum.io) +-- Forum: Python Coding (https://python-forum.io/forum-7.html) +--- Forum: Homework (https://python-forum.io/forum-9.html) +--- Thread: HELP - Calculating the complexity of my algorithm. (/thread-14953.html) |
HELP - Calculating the complexity of my algorithm. - Kokuzuma - Dec-26-2018 Hello, I am a student and a beginner in learning python coding, and I'm stuck on a list-binary exercice, where I'm asked to give the complexity of the Comptage function taking as an argument a list L, having to give in a new list the number of 0 and the number of 1 in L, relatively to the size p of L. Thus, I made the function : def Comptage(L) : ls1=[] ls2=[] ls3=[] ls4=[] sommels3=0 sommels4=0 ls5=[] for v in L : ls1.append(str(v)) for k in ls1 : for x in k : ls2.append(int(x)) for s in ls2 : if s==0 : ls3.append(1) elif s==1 : ls4.append(1) for w in ls3 : sommels3+=w ls5.append(sommels3) for p in ls4 : sommels4+=p ls5.append(sommels4) return(ls5)But when I started to calculate the total cost of it, other parameters are added, other than the size p of the list L. I arrived at this : 7 + 2p + 2pq + 4q + (1 + y) x + 1 + (1 + z) x + 1 + 1 = p (2 + 2q) + 4q + (2 + y + z) x + 10 with p the size of the list L, q the number of values composing the values of the list L, y the number of sums made to establish the value of sommels3, and z the number of sums made to establish the value of sommels4. I think there is surely a way to make my algorithm simpler, is it the solution to remove the other parameters, other than p ? Thank you in advance. RE: HELP - Calculating the complexity of my algorithm. - micseydel - Dec-26-2018 If the bit-strings have a bounded/"constant" length then it's just O(len(L)). Otherwise it's O(sum(map(len, L))) if you treat L as having real bit-strings instead of numbers. By the way, you have a lot of indirection in your code. You create lists and append 1 to them to later add those 1s to a counter. You can skip putting 1s in the lists and just increment the counter directly. I would also in-line the str() call, no need for an extra list there. RE: HELP - Calculating the complexity of my algorithm. - micseydel - Dec-26-2018 I didn't test it but I think your code can be simplified to something like this def Comptage(L) : zeros = 0 ones = 0 for x in L: for digit in str(x): if digit == 0: zeros += 1 elif digit == 1: ones += 1 return [zeros, ones] |