Python Forum
HELP - Calculating the complexity of my algorithm.
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
HELP - Calculating the complexity of my algorithm.
#1
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.
Reply
#2
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.
Reply
#3
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]
Reply


Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020