再帰的Big-Oの複雑さ

Question

私は明日コンピュータサイエンスを持っており、これらの再帰関数の複雑さを判断するのに役立つ必要があります。私は単純なケースを解決する方法を知っていますが、私はまだこれらの困難なケースを解決する方法を学ぼうとしています。どんな助けでも大いに感謝して、私の研究で大きく助けてくれるでしょう、ありがとう！

fonction F(n) 
    if n == 0 
     return 1 
    else 
     return F(n-1) * n 

fonction UniqueElements(A[0..n-1]) 
    for i=0 to i <= n-2 do 
     for j=i+1 to j <= n-1 do 
      if A[i] == A[j] 
       return false 
     return true 

fonction BinRec(n) 
    if n == 1 
     return 1 
    else 
     return BinRec(floor(n/2)) + 1 

Answer 1

学習の手助けのために、関数をプログラムに組み込み、最悪の場合のシナリオのパフォーマンスをテストできます。手でOを計算しようとすると

は、ここに

• +、覚えておくことがいくつかある - 、*、および/オフセットは無視することができます。したがって、1〜n + 5と1〜5nは、1〜nと同等と見なされます。
• また、O 2^n + n^2 + nの場合、2^nが最も速く成長するので、O 2^nと同等です。
• 再帰関数では、メソッド内で関数が呼び出された回数（分割数）と呼び出しに必要な量（深さは通常はリストの長さに等しい）を調べています。最終的なOはdepth_count^split_countになります
• ループでは、入れ子になったループはそれぞれのループに乗算され、逐次ループが加算されるので、（1-n）{（1-n）{}}（1-n） {}は（n * n）+ n）=> n^2 + n =（最も高い成長カウントのみ）> n^2
• 実践！成長率のガッチャとコントロールフローがどのように作用するかを知るためには、練習をする必要があります。 （そうオンライン実際にquiz秒を行う）

function F(n){ 
 
    count++ 
 
    if (n == 0) 
 
     return 1 
 
    else 
 
     return F(n-1) * n 
 
} 
 

 
function UniqueElements(A){ 
 
    for (var i=0 ; i <= A.length-2; i++){ 
 
     for (var j=i+1;j <= A.length-1; j++){ 
 
      if (A[i] == A[j]){ 
 
       return false 
 
      } 
 
     } 
 
    } 
 
       
 
return true 
 
} 
 

 
function BinRec(n) { 
 
    count++ 
 
    if (n == 1) 
 
     return 1 
 
    else 
 
     return BinRec(Math.floor(n/2)) + 1 
 
} 
 

 
count = 0; 
 
console.log(F(10)); 
 
console.log(count); 
 
count = 0; 
 
console.log(UniqueElements([1,2,3,5])); 
 
console.log(count); 
 
count = 0; 
 
console.log(BinRec(40)); 
 
console.log(count);