Мне сказали сделать функцию на основе цикла, которая возвращает n-е число Фибоначчи. Я уже сделал функцию и включу ее ниже. В моем задании говорится: «Утверждать, что время работы функции равно Θ(n), т. е. функция линейна по n». В книгах, которые я читал, и видео, которые я смотрел, Big-Theta всегда записывалась как Θ(g(n)) и выражалась в виде некоторого неравенства. Инструктор отказывается отвечать на какие-либо вопросы по этому поводу, пока мы не сдадим его.
Вот два моих вопроса:
1) Буду ли я прав, если скажу, что мой g(n) равен 5n+7 и что Θ(n) линейно, потому что g(n) линейно?
2) Нужно ли мне беспокоиться о верхних и нижних границах, даже если эта функция имеет линейное время выполнения?
int fib(int n)
{
int fib = 1; //1
int num1 = 0; //1
int num2 = 1; //1
for(int i = 0; i < n; i++) // 1 + (n+1) + 1
{
fib = num1 + num2; //2n
num1 = num2; //1n
num2= fib; //1n
}
return fib; //1
} //----------------
//5n+7 <- runtime as a function of n
Насколько я понимаю, не будет никаких верхних или нижних границ, потому что время выполнения линейно.
n
раз. - person SkryptX   schedule 17.07.2017