Какова временная сложность этой функции с помощью встроенной функции?

Question

Предположим, у вас есть следующая функция compute, использующая встроенную в Python функцию sum:

def compute(a_list):
    for i in range(0, n):                        #Line 1
        number = sum(a_list[0:i + 1])/(i+1)      #Line 2
    return number

Как бы выглядела сложность времени для чего-то подобного?

Line 1 выполняется n раз, но Line 2, имеющий встроенную функцию sum (O (n)), будет ли выполняться n ^ 2 раза?Следовательно, алгоритм будет O (n ^ 2).

Для каждой итерации i, Line 2 выполняется 1 + 2 + 3 + ... + n-2 + n-1 + n.Сумма этих терминов составляет

Это правильно?

Answer 1

Я бы сказал, что строка 1 выполняется один раз, и это приводит к тому, что строка 2 выполняется n раз.индекс списка O (n), а sum также O (n).деление, сложение и присвоение - все O (1).

compute, следовательно, O (N ^ 2), так как самые большие члены оценивают O (n) операцию O (n) раз.

обратите внимание, что, как написано, он отбрасывает все промежуточные результаты, поэтому его можно переписать как:

def compute(a_list):
    return sum(a_list[0:n])/n

, что будет O (n).