ループのビッグシータ記号と時間複雑度

Question

フィボナッチ数を返すループベースの関数を作成するように指示されました。私はすでにその機能を作っており、それを下に含めます。私の割り当ては、「関数の実行時間がΘ（n）である、すなわち関数がnで線形であると主張する」と述べている。私が読んだ本や、私が見たビデオでは、Big-Thetaは常にΘ（g（n））と書かれていて、何らかの不等式として表現されています。インストラクターは、私たちがそれを回すまでこのについての質問に答えることを拒否した。ここ

は私の二つの質問です：。

1）私は私のG（n）は7 + 5Nで、Θということを言って、正しいだろう（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であり、g（n）は線形なのでΘ（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)で終わります。ランタイムが正確にnであり、でなくても最大でnであるため、私はBig-Thetaを使用し、O表記は使用しないことに注意してください。