深い制限で再帰アルゴリズムの複雑さを計算する

Question

おはようございます、私は再帰呼び出しを行う際にアルゴリズムと複雑さを計算する方法を研究していますが、再帰呼び出しのレベル制限が複雑さの計算にどのように影響するかについてのリファレンスは見つかりません。たとえば、次のコードは

countFamilyMembers(int level,....,int count){ 
     if(noOperationCondition) { // for example no need to process this item because business rules like member already counted 
      return count; 
     } else if(level >= MAX_LEVEL) { // Level validation, we want just to look up to certain level 
      return ++count //last level to see then no more recurrence. 
     } else { 
      for (...each memberRelatives...) { //can be a database lookup for relatives to explore 
       count = countFamilyMembers(++level,...,++count); 
      } 
      return count; 
     } 
    } 

私はこれがO（2^n）ループ内の再帰呼び出しだと思います。しかし、私は2つの主な質問があります： 1.ループの値が元の入力とまったく関係していないとどうなりますか？それも "n"と考えることができますか？ 2.レベルの検証は、再帰呼び出しを制限して切断することです。これが複雑な計算にどのように影響しますか？

Answer 1

ありがとうございます。だから私たちはnをいくつかの親戚の "ベストメトリック"と取るでしょう。これはいくつかのパラダイムでは「ファンアウト」としても知られています。

したがって、あなたはレベル0で1人、レベル1のN、レベル2ののn^2、などがあるでしょう。戻り値と操作数（ノード訪問、増分など）の概算は、レベル範囲0〜MAX_LEVELに対してn ^レベルの合計です。支配的な項は、最も高い指数、n^MAX_LEVELです。

私はあなたの答えです：O（n ^^ MAX_LEVEL）、a.k.a.多項式時間。もしNの値を与えることが起こる場合、Nに対しても上限、これは一定となり、複雑さがO（1）である、ことを

注。