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

Question

我被告知要制作一个基于循环的函数，returns 第 n 个斐波那契数。我已经制作了该功能并将其包含在下面。我的作业是 "argue that the running time of the function is Θ(n), i.e. the function is linear in 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) Would I be correct in saying that my g(n) is 5n+7 and that Θ(n) is linear because g(n) is linear?

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

要了解 O(g(n)) 和 Θ(g(n)) 之间的区别，请看这里：What is the difference between Θ(n) and O(n)?

2) Do I need to worry about upper and lower bounds even though this function has a linear runtime?

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

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

Big Theta notation and time complexity of a loop

big-theta

asymptotic-complexity