Мне было предложено определить и решить повторение T (n), а также представить его в нотации Big-O, но я смущен этими двумя переменными. Я думаю, что имею дело с f(m,n) = 1 + f(m+1,n-3) за n>1, а f(1) = m+10 - мой базовый шаг? Но кроме этого я не уверен.Определить повторяемость с двумя переменными
int f(int m, int n)
{
if (n<=1)
return m+10;
else
return 1+f(m+1,n-3);
}
Проблема может быть решена в O (1) времени. Решение зависит только от значения n.
f(m,n) = 1+f(m+1,n-3) for n > 1
и
f(m,1) = m+10
Теперь это можно записать следующим образом,
е (т, п) = & lfloor; п/3 & rfloor + т + & lfloor; п/3 & rfloor; +10 , который равен,
е (т, п) = 2 & lfloor; п/3 & rfloor + т + 10
код C для функции также приводится ниже,
int f(int m, int n)
{
return (2*(n/3)+m+10);
}
Ваша формула подходит только 67% времени. – user3386109
Вы говорите: 'е (п, т)', а затем сделать 'Int F (ИНТ м, Int N)' вы уверены, что ваш выражение верно? – Surya
Итак, теперь 'f (1)' вы имеете в виду 'n = 1', так как в условии, вы возвращаете его на основе значения' n', я полагаю. Не могли бы вы описать возможное значение 'm' в этом случае? – Surya
Обратите внимание, что время выполнения этой вещи не зависит от m. в частности, вы имеете T (m, n) = 1 + T (m + 1, n-3), T (a, 1) = T (a, 0) = T (a, -1) = 1. может быть что угодно. R (n) = 1 + R (n-3) (с R (n) = T (m, n)) и R (1) = R (0) = R (-1) = 1. Время выполнения T (m, n) равно ceil ((n + 1)/3). – thang