Для типичной факториальной функции, подобной этой, тета-нотация есть тета (n), потому что она растет с постоянным линейным временем.
int factorial(int n)
{
if (n == 0)
return 1;
else
return n * factorial(n - 1);
}
Для рекурсивной функции, подобной приведенной ниже, обозначение big-O равно O (n ^ 2):
int mystery(int n)
{
int res = 0;
for (int i = 0; i < n; i += 2)
res += 1;
if (n <= 0)
return res;
else
return res * mystery(n - 1);
}
Будет ли тэта-обозначение тайны (n) также тэта (n ^ 2)? Я запутался в том, какие предположения я могу сделать о тета-нотации здесь. Спасибо за любую помощь.
Задача ещё не решена.
Других решений пока нет …