почему сложность времени T (n) = 2n ^ 2 + n + 1?

Question

T (n) = 2n ^ 2 + n + 1 Я понимаю, 2n ^ 2 и 1 части, но я запутался в n.

test = 0
for i in range(n):
    for j in range(n):
        test = test + i*j

Answer 1

Это на самом деле зависит от того, как ваш профессор / книга действительно сократит операционные расходы, но я думаю, что мы можем как-то понять это отсюда.Давайте сломать 2n^2 + n + 1 вниз.n^2 происходит из двух циклов.

for i in range(n):
    for j in range(n):

Коэффициент 2 предположительно происходит из двух операций.Примечание: это только сложность с постоянным временем AKA O (1)

test = test + i * j

Первоначальный расчет range(n) может стоить n (в вашем расчете + n).Затем второй вызов range(n) может быть оптимизирован для использования кэшированного значения.

Наконец, это может быть оператор test = 0, в начале может быть + 1.Это может составить 2n^2 + n + 1.Тем не менее, временная сложность в худшем случае все еще составляет O(n^2).