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。