Как рассчитать временную сложность вложенного цикла for?

Question

Рассмотрим:

def fun(n):

    for i in range(1, n+1):
        for j in range(1, n, i):
            print (i, “,”, j)

У меня проблемы с вложенным циклом for.Это 2n ^ 2 + 2n + 1?

Answer 1

Внутренний цикл выполняется от 1 (включительно) до n (эксклюзив) в прыжках i.Таким образом, это означает, что он будет совершать (n-1)//i шагов.

Внешний цикл выполняет n прогонов, где i колеблется от 1 до n.Мы можем немного переоценить общее количество шагов, рассчитав количество шагов как сумму:

 n                    n
---                  ---
\     n-1            \    1
/     ---    = n-1 * /   ---
---    i             ---  i
i=1                  i=1

Здесь мы можем использовать приближение Стирлинга: мы знаем, что интеграл, если 1 / i будет между суммой 1 / (i + 1) и 1 / i .

Интеграл 1 / i ,таким образом, мы приближаем это как:

 n         n
---        /\
\    1     |    1
/   ---  ≈ |   --- dx  = log(n) - log(1)
---  i    \/    x
i=1        1

Таким образом, это означает, что общее количество шагов, в терминах большого ой O (n log n) .

Answer 2

Сложность вашего кода O(n log n).Внутри первого цикла for сложность составляет O(n/i), что в сумме составляет:

O(n/1) + O(n/2) + ...+ O(n/i)+...+O(1)

. Это равно:

n O( 1 + 1/2 + ... + 1/n ) = n O(log(n)) = O(n log(n))

.