Мне дали псевдокод, чтобы найти рекуррентные отношения и асимптотическую жесткую границу, и я не могу понять, как даже попытаться понять, как с этим бороться.
Calc_a(n):
if n==1:
return 1
sum = 0
for i = 1 to n−1
sum = sum + calc_a(i)
return sum
Прежде всего, как я уже сказал, меня попросили найти формулу отношений рекуррентности для этого кода, и я попытался решить ее, следуя тому, что код делает для нескольких входных данных.
Я полагал, что он возвращает вдвое больше, чем в прошлый раз. (за исключением случаев 1 и 2, где он возвращает 1 в обоих).
Так что я подумал про себя - вероятно, это будет что-то вроде этого:
T(n) = 2*T(n-1) + c
так как сумма, которую он возвращает, равна количеству вызовов метода, я добавил c в качестве константы, чтобы показать количество «однострочных работ», выполненных за каждую итерацию. (т.е. строки if-else и sum =).
Проблема в том, что это не соответствует тому, что они просят меня сделать во второй части:
Найти плотную асимптотическую оценку для отношения Hint:look both at T(n) and at T(n + 1) at the same time
Но с помощью отношения, которое я нашел, очень легко доказать, что оно Omega(2^n), а также не так сложно доказать, что оно BigO(2^n).
Любая помощь? заранее спасибо. :)