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

Question

[tiakuv]

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

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

Answer 1

[ayazer]

сложность обоих решений O(n), разница только в константе. Но в первом случае вы пробегаетесь по всему списку 1 раз, и сразу считаете все что нужно. во втором - вы это делаете 3 раза. Ну и да - во втором случае вы еще и память выделяете.

Comments

[tiakuv]

не очень понимаю про выделение памяти во втором случае, объясните пожалуйста

[Ivan Yakushenko]

tiakuv, в первом случае ты просто итерируешь существующий список, во втором ты создаешь новый, соответственно выделяется память.

[tiakuv]

Ivan Yakushenko, поняла, спасибо

[ayazer]

tiakuv,
[x for x in lst if x > 0]
= создание нового массива (о чем уже и успели написать)

[Алексей Кулаков]

где ж тут O(n) во втором случае? три прохода по всей коллекции это O(3n). да, оба алгоритма с линейной сложностью но эффективнее однозначно первый

[ayazer]

Алексей Кулаков, О-нотация это аппроксимация. Потому О(3n) = O(kn) = O(n) т.к. все 3 случая линейные, а разница только в константе

[Алексей Кулаков]

ayazer ну окей, это говорит опять-таки о линейной зависимости от входных данных. если обе зависимости линейны то эффективность двух алгоритмов будет зависеть все же от констант. Или вы утверждаете что алгоритмы с k = 1 и k = 100 равнозначо эффективны?

[ScriptKiddo]

Алексей Кулаков, Big-O нотация не про эффективность. Только лишь про зависимость роста времени выполнения от размера входных данных.

[xmoonlight]

Алексей Кулаков, y=kx+b - это линейная функция, поэтому сложность O(n).
Хотя, я согласен, что "разброс" эффективности тут - огромный.

Подробно - на википедии, раздел "Примеры использования".

[ayazer]

Алексей Кулаков, мне кажется вы невнимательно прочитали мой ответ. Я специально уточнил что у них разные константы. И даже описал почему у них константы будут разные. Да, это безусловно влияет на реальное выполнение алгоритма, но этот вообще никак не влияет на О. О(n) говорит только о факте линейного роста чего-то от кол-ва входных данных. Будет это n или 100n - рост все-равно будет линейный.

Answer 2

[Developer]

Первое эффективнее.
Синтаксический сахар под капотом подразумевает дичайшие перетурбации, зачастую неэффективные. Бывают хорошие оптимизаторы, но полагаться на них не стоит.
К тому же, во втором случае пробегаем три раза, O(3n).
Это вопрос для собеседования. Люблю такие вопросы задавать, чтобы понять, тянет ли кандидат хотя бы на джуниора или нет.
А дальше идут вопросы про классы, ООП, интерфейсы и прочее

Comments

[javedimka]

И шо, кем питон разработчик который на вопрос про интерфейсы ответил у тебя становится?

[tiakuv]

Не по теме вопроса, но к вашему комментарию: а про паттерны проектирования спрашиваете?

Answer 3

[Алексей Кулаков]

Давай ты будешь думать логически сам?

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

Comments

[tiakuv]

в первую очередь сама подумала) мне нужно было подтверждение правильности моих мыслей