T
T
tiakuv2020-07-31 10:49:24
Python
tiakuv, 2020-07-31 10:49:24

With t.z. complexity of the algorithm list generator is similar to a loop? O(n)?

On the example of the task:
Count the number of positive, negative numbers and zeros in the array. Print the relation to the size of the array on a separate line.
Which solution will be more efficient?

def plusMinus(arr):
    pos = 0
    neg = 0
    nul = 0

    for a in arr:
        if a > 0:
            pos += 1
        elif a < 0:
            neg += 1
        else:
            nul += 1
          
    print ("%.6f\n%.6f\n%.6f" % (pos/len(arr), neg/len(arr), nul/len(arr)))


OR

print format(len([x for x in lst if x > 0])/n, ".6f")
print format(len([x for x in lst if x < 0])/n, ".6f")
print format(len([x for x in lst if x == 0])/n, ".6f")

Answer the question

In order to leave comments, you need to log in

3 answer(s)
A
ayazer, 2020-07-31
@tiakuv

the complexity of both solutions is O(n), the difference is only in the constant. But in the first case, you run through the entire list 1 time, and immediately consider everything you need. in the second - you do it 3 times. Well, yes - in the second case, you also allocate memory.

D
Developer, 2020-07-31
@samodum

The first is more efficient.
Syntactic sugar under the hood implies the wildest returbations, often inefficient. There are good optimizers, but you should not rely on them.
In addition, in the second case we run three times, O(3n).
This is an interview question. I like to ask such questions in order to understand whether the candidate is at least a junior or not.
And then there are questions about classes, OOP, interfaces, and so on.

A
Alexey Kulakov, 2020-07-31
@carbon88

Come on, will you think logically yourself?
How many passes through the data array (cycles) do you see in the first and second options?

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question