大θ符号和循环的时间复杂度

Question

我被告知要创建一个基于循环的函数，返回第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

据我了解，没有上限或下限，因为运行时是线性的。

Answer 1

1(我说我的g(n(是5n+7，而Θ(n(是线性的，因为g(n(是线性的，这是否正确？

是的，有点。我不鼓励你说出某个g(n)，因为要明白编程语言不是数学函数的良好表示。你可以以递归的方式对函数进行编程，并进行完全不同的分析，或者以你的方式甚至是不可能的。但保持不变的是，您的算法始终满足O(n)并且与Θ(g(n))成正比g(n) = n.

要了解O(g(n))和Θ(g(n))之间的区别，请看这里：Θ(n(和O(n(之间有什么区别？

2(即使这个函数有线性运行时，我是否需要担心上限和下限？

不，你没有。不在此算法中。斐波那契算法中没有更好或更坏的情况，因此它将始终以Θ(n)结束。请注意，我使用了 Big-Theta 而不是 O 表示法，因为您的运行时完全n，最多不是n。