Big Theta表示法和循环的时间复杂度

Question

我被告知要创建一个基于循环的函数，该函数返回第n个斐波那契数。我已经完成了这个功能，并将其包含在下面。我的任务说“要求函数的运行时间是Θ（n），即函数在n中是线性的”。在我看过的书和我看过的视频中，Big-Theta总是写成Θ（g（n）），并表示为一些不平等。导师拒绝，直到我们把它回答任何相关的问题

这里是我的两个问题：

1）请问我在说我克（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))的区别看这里：What is the difference between Θ(n) and O(n)?

2）我需要担心的上限和下限，即使该功能具有线性运行？

不，你不知道。不在这个算法中。在斐波那契算法中没有更好或更糟的情况，所以它总是以Θ(n)结束。请注意，我使用了Big-Theta而不是O-notation，因为您的运行时间是完全的n而不是最多n。