Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Алгоритмы и теория программирования

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 295 RSS
←   Июнь 2021   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rfpro.ru/
Открыта: 11-11-2009

Автор
Калашников О.А.

Статистика

295 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Алгоритмы и теория программирования


РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты в разделе

Алексеев Владимир Николаевич
Статус: Мастер-Эксперт
Рейтинг: 316
∙ повысить рейтинг » 		CradleA
Статус: Мастер-Эксперт
Рейтинг: 278
∙ повысить рейтинг » 		solowey
Статус: Академик
Рейтинг: 104
∙ повысить рейтинг »

Алгоритмы и теория программирования

Номер выпуска:241
Дата выхода:14.06.2021, 20:45
Администратор рассылки:Зенченко Константин Николаевич (Старший модератор)
Подписчиков / экспертов:2 / 16
Вопросов / ответов:1 / 1

Консультация # 201135: Здравствуйте! Прошу помощи в следующем вопросе: Задание на фото:...

Консультация # 201135:

Здравствуйте! Прошу помощи в следующем вопросе:
Задание на фото:

Дата отправки: 09.06.2021, 20:40
Вопрос задал: lyskov.kirill (Посетитель)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует vsetin (Студент):

Понадобятся две формулы:

1) для суммы арифметической прогрессии S = a1 + a2 + ... + ak = (a1+ak)·k/2
2) для суммы квадратов натуральных чисел от 1 до k: 12 + 22 + 32 +...+k2 = k·(k+1)·(2·k+1)/6

Вторая формула не очень известна. При желании ее можно доказать методом математической индукции.

Обратим внимание, что численно r будет равно количеству раз, которое выполняется k в программе. Значит, ищем сколько раз выполнится k в программе.

Смотрим на внутренний цикл (с к). При фиксированном j он выполняется ровно j раз. То есть нашли, сколько раз выполняется цикл k при фиксированном j.

Но ведь j меняется! Поэтому теперь смотрим на цикл с j. Первое значение j равно (i+1), потом (i+2) и т.д. до n. Значит, внутренний цикл k выполнится сначала (i+1) раз, потом (i+2) раз и т.д. до n раз. А в сумме это равно:

S = (i+1 ) + (i+2) + (i+3) + ... n, т.е. сумма арифметической прогрессии от (i+1) до n. Всего членов (n - (i+1) + 1) = (n-i). Значит, используя вышеуказанную формулу, получаем:

S = { (i+1) + n}·(n-i)/2 = (n+i+1)·(n-i)/2 = (n2 - i2 + n - i)/2 = (n2 + n)/2 - (i2 + i)/2, т.е. сгруппировал отдельно члены, зависящие и не зависящие от i.

Таким образом, нашли, сколько раз выполняется внутренний цикл k при фиксированном i. Поскольку i тоже меняется, то теперь смотрим на цикл с i.

Значения i меняются от 1 до n-1. Значит, ищем сумму с этими пределами:

Σ{ (n2 + n)/2 - (i2 + i)/2} = Σ(n2 + n)/2 - 1/2·Σ i2 - 1/2·Σ i =
=(n-1)·(n2 + n)/2 - 1/2·1/6·(n-1)·n·(2·n-1) - 1/2·n·(n-1)/2 =
(то есть использовали обе вышеуказанные формулы и учли, что k=n-1)
= (n-1)/12·{ 6·n2 + 6·n - 2·n2 + n - 3·n}= (n-1)/12·{ 4·n2 + 4·n}=
= (n-1)/12·4·n·(n+1) = n·(n2 - 1)/3 = n3/3 - n/3

ОТВЕТ: n3/3 - n/3. Получается О(n3).

Консультировал: vsetin (Студент)
Дата отправки: 09.06.2021, 22:42 style="font-style: italic; color: gray;">нет комментария
-----
Дата оценки: 10.06.2021, 11:05
Рейтинг ответа:

НЕ одобряю +2 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!
В избранное