Асимптотическая сложность питона

Question

У меня есть задача найти асимптотическую сложность этого кода Python.

for i in range(x):
    if i == 0:
        for j in range(x):
            for k in range(500):
                print("A ")

По тому, что я знаю, это должно быть 500* х. Поскольку первый цикл идет только один раз (i==0), второй - x раз, а третий - 500 раз, поэтому он должен быть 500* x, не так ли? Однако это не правильный ответ. Не могли бы вы помочь мне?

Answer 1

Асимптотическая сложность описывает рост времени выполнения, когда переменные факторы растут произвольно большими. Короче говоря, добавленные или умноженные константы вообще не учитываются, поскольку они не меняются в зависимости от переменной.

Да, напечатано 500* х строк. У вас также есть х-1 итерации нефункциональных циклов. Ваше общее время будет вычислено как что-то вроде

(x-1) [накладные расходы цикла] + x [накладные расходы цикла] + 500*x[накладные расходы цикла + время печати]

Однако издержки цикла, будучи константой, незначительны и выпадают из выражения сложности. Аналогично, 500 - это просто коэффициент масштабирования, и он также исключается из выражения.

Сложность O (x).

Answer 2

Это 501* х, так как вы также должны проверить х раз линию if i == 0,

Как говорит другой ответ, обычно мы не учитываем этот фактор. Но иногда мы делаем.