Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Не получается решить задачу на анализ алгоритма(задача из книги Стивена Скиена "Алгоритмы. Руководство по разработке.")

Дима Рогатнев Рогатнев Ученик (78), на голосовании 1 год назад
Какое значение выведет следующая функция? Ответ должен быть в форме функции числа n. Найдите время исполнения в наихудшем случае, используя О-большое.

Функция на python:

def F(n):
----r = 0
----for i in range(1, n + 1):
--------for j in range(i + 1, n + 1):
------------for k in range(i + j - 1, n + 1):
----------------r += 1
----return r
Голосование за лучший ответ
drtjjrt drtjrt Профи (620) 1 год назад
Функция вычисляет количество итераций, которое происходит во вложенных циклах. Внутренний цикл k работает O(n - i - j + 1) раз на каждой итерации внешнего цикла j, а внешний цикл j работает O(n - i) раз на каждой итерации внешнего цикла i. Следовательно, время работы данной функции в наихудшем случае составляет O(n^3).

Для нахождения значения, которое вернет функция, можно вычислить количество итераций, которое будет выполнено в циклах. Рассмотрим сначала внутренний цикл k. Поскольку k должен быть не меньше, чем i+j-1 и не больше, чем n, то количество итераций в цикле k на i-ой итерации внешнего цикла j будет равно n - (i + j - 1) + 1, или n - i - j + 2. Тогда количество итераций внутреннего цикла k при фиксированных значениях i и j будет равно сумме от (n - i - j + 2) до n, или (n - i - j + 2) * (n - i - j + 3) / 2. Заметим, что i+1 должно быть меньше, чем n, поэтому j не может начинаться с n-1. Аналогично, i не может начинаться с n-2. Используя эти ограничения, мы можем найти сумму всех итераций в циклах и получить ответ:

def F(n):
r = 0
for i in range(1, n - 1):
for j in range(i + 1, n):
r += (n - i - j + 2) * (n - i - j + 3) // 2
return r

Например, F(4) вернет 16, потому что есть 16 итераций во внутренних циклах:

(i=1,j=2,k=3),(i=1,j=2,k=4),(i=1,j=3,k=4),(i=2,j=3,k=4)
(i=2,j=1,k=2),(i=2,j=1,k=3),(i=3,j=1,k=2),(i=3,j=1,k=3)
(i=2,j=4,k=4),(i=3,j=4,k=4),(i=1,j=4,k=4),(i=1,j=3,k=3)
(i=1,j=2,k=2),(i=2,j=3,k=3),(i=2,j=4,k=3),(i=3,j=4,k=3)

Общее количество итераций равно 16.
Дима Рогатнев РогатневУченик (78) 1 год назад
Вроде бы функция проитерируется только 7 раз (результат функции F(4)), а ваш вариант 10 раз (результат функции F1(4))
Дима Рогатнев Рогатнев, думаешь, биоробот, скопировавший ответ нейросети, понял хоть слово из твоего вопроса и твоего комментария? Он умеет только копировать. Первый отвечающий правильно написал: сложность - кубическая, O(n³).
Похожие вопросы