@adilet_murzaliev

Сумма арифметической прогрессии?

Подскажите пожалуйста, как вывели сокращения этой суммы:
616c7dad3d979788414568.png
Что-то никак не могу понять (привести), как получилось O(n^3). Или это просто допущение...
  • Вопрос задан
  • 169 просмотров
Решения вопроса 2
wataru
@wataru Куратор тега Математика
Разработчик на С++, экс-олимпиадник.
Выражение под суммой, отмеченное красным на картинке - это сумма арифметической прогрессии, вы же сами написали.

Первый член - 1 (при j=i+1), последний - n-i (при j=n). Всего их n-i. Ну а дальше - стандартная формула: среднее крайних членов, помноженное на их количество.

Как из этого получается O(n^3). По уму, надо раскрыть скобки и разложить на сумму трёх рядов, в зависимости от степени i в слагаемом. Дальше сумма i даст также O(n^2). Сумма по i^2 даст O(n^3). Тут уже нельзя арифметическую прогрессию применять, но это известная формула - сумма n квадратов даст n(n+1)(2n+1)/6. Ее можно вывести, если взять ряд f(x)=1+x+x^2+...+x^n = (1-x^{n+1})/(1-x) и найти (x*f'(x))'. Потом туда можно подставить x=1. Или есть визуальные доказательства. Каждый квадрат - это квадрат из кубиков. Их все можно сложить в пирамиду. 6 таких пирамид можно сложить в параллелепипед.
Ответ написан
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Внутренняя сумма раскладывается как 1 + 2 + 3 + ... + n - i = (1 + n - i) * (n - i) / 2
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
ModuleWorks Симферополь
от 600 до 2 000 €
RefleXion Medical Санкт-Петербург
от 160 000 до 220 000 ₽
PrimatLab LLC Таганрог
от 90 000 до 120 000 ₽
30 нояб. 2021, в 21:14
5000 руб./за проект
30 нояб. 2021, в 20:09
20000 руб./за проект
30 нояб. 2021, в 19:40
4000 руб./за проект