def program2(L):
squares = []
for x in L:
for y in L:
if x == y:
squares.append(x*y)
return squares
нет шагов, предпринятых в худшем случае по мне это 4*n^2 + 2, но ответ на этот вопрос является 4*n^2 + 2 + n и объяснение, как следоватьНет шагов, предпринятых в худшем случае
В худшем случае, L представляет собой длинный список одного повторного числа (то есть [2, 2, 2, 2, ...]). В этом случае мы проходим через цикл для x в L n раз. Каждый раз через этот цикл мы выполняем одно присваивание значения переменной x, затем выполняем внутренний петля для y в L n раз.
Внутренний цикл выполняет одно присвоение значения переменной y. Затем он имеет одну операцию, которая проверяется каждый раз (если x == y). Поскольку случай WORST - это когда список состоит из одинаковых элементов, эта проверка всегда верна, поэтому всегда выполняются третья и четвертая операции (x*y и список). Таким образом, внутренний цикл выполняет на каждой итерации внешнего цикла 4*n раз. Таким образом, структура вложенных циклов выполняется n * (4*n + 1) = 4*n**2 + n раз!
Добавление в два этапа (для первого оператора присваивания и оператора return) мы видим, что в худшем случае эта программа выполняет 4*n**2 + n + 2 шагов.
Почему мы добавляем + 1 (4n + 1). Невозможно понять это, потому что ни один из выполненных шагов не является 4n (включая внутренний цикл и шаги шагов внутри него).
Какие предположения вы делаете? Должна ли эта проблема рассматривать внутренние компоненты Python? Поскольку временная сложность здесь была бы просто O (n^2). Что вы считаете шагом? –
Я думаю, что ваш учитель переусердствует. Скажите им также рассмотреть вопрос о том, как происходит умножение, а затем «шаги» изменяются в зависимости от этого алгоритма + количество цифр. –
В этой задаче мы должны рассчитывать количество шагов, выполняемых в худшем случае. Не сложность в асимптотической нотации – Batman007