Как найти сложность времени для заявления, которое умножается на

Question

Я студент, пытающийся проанализировать временную сложность следующего фрагмента псевдокода

function stars(A):
    for i in [1:n]:
        print ’*’ i many times

Разве временная сложность для этого не должна быть O (n)? Там только 1 'для' l oop. Решение для этого говорит его O (n ^ 2).

Answer 1

Я подозреваю, что ваш псевдокод

print '*' i много раз

означает, что код выполняет дополнительный l oop. Это означает, что с учетом n вы печатаете n раз для каждого вхождения в [0, n]. Таким образом, n * n, который дает вам результат O (n ^ 2).