@tiakuv

С т.з. сложности алгоритма генератор списка аналогичен циклу? O(n)?

На примере задачи:
Подсчитать в массиве кол-во положительных, отрицательных чисел и нулей. Вывести отношение к размеру массива на отдельной строчке.
Какое решение будет эффективнее?

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)))


ИЛИ

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")
  • Вопрос задан
  • 105 просмотров
Решения вопроса 1
@ayazer
Sr. Software Engineer
сложность обоих решений O(n), разница только в константе. Но в первом случае вы пробегаетесь по всему списку 1 раз, и сразу считаете все что нужно. во втором - вы это делаете 3 раза. Ну и да - во втором случае вы еще и память выделяете.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
samodum
@samodum
Какой вопрос - такой и ответ
Первое эффективнее.
Синтаксический сахар под капотом подразумевает дичайшие перетурбации, зачастую неэффективные. Бывают хорошие оптимизаторы, но полагаться на них не стоит.
К тому же, во втором случае пробегаем три раза, O(3n).
Это вопрос для собеседования. Люблю такие вопросы задавать, чтобы понять, тянет ли кандидат хотя бы на джуниора или нет.
А дальше идут вопросы про классы, ООП, интерфейсы и прочее
Ответ написан
@carbon88
.NET developer/ORM developer
Давай ты будешь думать логически сам?

Сколько проходов по массиву данных (циклов) ты видишь в первом и во втором варианте?
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы