+- 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]