Почему сложность алгоритма (n+2n+3n+…+n⋅n) = O(n³)?

Question

[Савва Насыров]

Насколько я понимаю- самый простой путь для решения будет примерно такой:

n = int(input())

summ = 0

for i in range(1,n+1):
    summ += i*n

тогда количество итераций цикла будет = n.

Но почему-то правильный ответ O(n³)

Comments

[Савва Насыров]

мой косяк, я имел ввиду алгоритм решения. Тогда количество базовых операций(обычно берется операция в цикле) будет = n

[Савва Насыров]

но до ответа n в 3 я никак не дохожу

[Akina]

Что, сумму чисел от 1 до N в школе не проходили, что ли?

(n+2n+3n+…+n*n) = n * (1+2+3+..+n) = n * (n * (n+1) / 2) = n*n*n/2 + n*n/2

При определении сложности слагаемые низших степеней и постоянные множители отбрасываются. И остаётся голенькое n^3.

[Shavadrius]

Самый простой способ посчитать - будет вбить формулу арифметической прогрессии, которая указана выше в комментарии. Сложность будет О(1) вообще)

Answer 1

[Василий Банников]

Не нужно путать big-O и алгоритм для подсчёта прогрессии.

Answer 2

[Wataru]

Я так понял, вопрос в том, почему O(n+2n+...+n^2) = O(n^3)?

Выписывать тут алгоритм для подсчета суммы в скобках вообще бессмыслено. Его сложность никак не связана с искомой. Это как для поиска длины строки, состоящей из цифр, считать их сумму или пытаться прочитать их как число. Ну бред же.

Надо применить математику, ибо O() - это математический объект. Как вам уже сказали, надо подсчитать сумму арифметической прогрессии в скобках и получится кубический многочлен от n. Далее, по свойствам, О-большое, это будет кубическая сложность.

Answer 3

[SeptiM]

На всякий случай, O -- это асимптотическая оценка сверху. Что-то типа '<='. Точная оценка определяется через \Theta, а нижня оценка `>=` через \Omega.

В целом, можно посчитать точно через через прогрессию:

n + 2n + 3n + … + n ⋅ n = n ⋅ (1 + ... + n) = n * n * (n + 1) / 2 = O(n^3) (и \Theta(n^3)

Можно лениво через верхнюю оценку:

n + 2n + 3n + … + n ⋅ n <= n * n + ... n * n (n раз) = n^3 = O(n^3)

Нижняя оценка оценивается по такому же принципу:

n + 2n + 3n + … + n ⋅ n >= n/2 * n + ... n * n (n / 2 раз) >= n / 2 * n / 2 * n = \Omeg(n^3)