-3 
int Do(int n)
{
 if(n<=2)
  return 1;
 else
 return(Do(floor(sqrt(n))+n);
}

再帰関係を次のように使用できますT(square root(n)+n))+1か? もしそうなら、どうすればこの問題をさらに進めることができますか?

4

2 に答える 2

1

あなたの質問のように再帰が終了することはありません（少なくとも理論的には、おそらくあなたが話していることです）。理由:n + floor(sqrt(n))より大きいn。

私はあなたが意味すると思いますreturn Do(floor(sqrt(n))) + n。この質問に答えるために一般的な考慮事項を続けますが、注意してください。自分で埋めなければならないギャップがいくつかあります。

実行時間に関する質問を 2 つの部分に分割します。

  • 最も重要: ベース ケースまでの再帰の回数は?
  • すべての再帰を組み合わせるには?

再帰の数: n2 の累乗として書きます (つまりn=2^(ld n)、ldは底 2 の対数を示します)。nrespの平方根を取る。2^(ld n)指数を半分にします。基本ケースに到達するには、指数が 1 未満になるまで指数を半分にする必要があります。ld nこれは、何かに到達するまでどのくらいの頻度で半減しなければならないかという疑問につながります<= 1。この質問に対する答えは、おおよそld ld nです。つまり、基本ケースまで大まかに ld ld n再帰があります。

ここで、再帰を実行して要約します。

T(n) = T(2^(ld 2))
     = T(2^((ld 2)/2)) + 1
     = T(2^((ld 2)/4)) + 1 + 1
     = ...
     = T(2^((ld 2)/(2^(ld ld 2)))) + sum(1, i=0...(ld ld 2)-1)
     = 1 + (ld ld 2) - 1

合計を単純化し、 - 部分の詳細を調整する必要がありfloorます。

于 2013-10-03T16:41:58.307 に答える
0

任意の数 n と n = 2^k を取ります。n の平方根は、指数の半分を意味します。したがって、O(log k) 平方根しか存在できません。

n =2^k したがって、k = log n . 次に、O(log k) は O(loglogn) に変わります ...

于 2013-10-03T17:06:05.157 に答える