私は今年10月にバイオインフォマティクスの修士号を取得しました。以前の生物学者は、コードから再帰方程式を見つけるのはかなり難しいです。誰かが私にこのことを説明できるなら、私はとても感謝しています。アルゴリズムの再帰方程式
このコードから再帰方程式を見つけるにはどうすればよいですか？
procedure DC(n)
if n<1 then return
for i <- 1 to 8 do DC(n/2)
for i <- 1 to n³ do dummy <- 0
条件を必要とする場合、ループの時定数cと第したがって、1から8まで行う再帰場合である第一ので私の推測は、T（n）は、C + 8T（N/2）=されます8 * T（n/2）、しかし、私は私の方程式にコードの最後の行を広告する方法を知らない。
あなたは近づいていますが、それほど大したことではありません。
通常、反復関係は、反復手続きの再帰的ステップによって行われる作業についてのみ記述します。これは、基本ケースが一定量の作業を行うと仮定しているからです。そのため、彼らが作っているもののサイズの入力作り、上でされている再帰的なものを呼び出し
あなたは、サイズn/2の入力に対して8つの再帰呼び出しがあることを正しく認識しているため、8T（n/2）項は正しいです。しかし、これがO（n ）の働きをするループに続いていることに注目してください。結果として、あなたの再帰関数をより正確
T（N）= 8T（N/2）+ O（N ）としてモデル化されます。
この再発はO（nはログN）に解決し、なぜあなたが主張することができればそれが見て、その後の価値があります。
あなたは私が始めたときに書きました...：）私はそれが遅い銃です – coderredoc
これはT(n)= 8*T(n/2)+O(n^3)であることが判明しました。
私は、これを反復/再帰ツリー方法で解く際にあなたにジャブを与えます。
T(n) = 8* T(n/2) + O(n^3)
~ 8* T(n/2) + n^3
= 8*(8* T(n/4) + (n/2)^3))+n^3
= 8^2*T(n/4)+8*(n/2)^3+ n^3
= 8^2*T(n/2^2)+n^3+n^3
= 8^2(8*T(n/8)+(n/4)^3)+n^3+n^3
= 8^3*T(n/2^3)+ n^3 + n^3 + n^3
...
= 8^k*T(n/2^k)+ n^3 + n^3 + n^3 + ...k time ...+n^3
これは、n/2^k=1 or k=log_2(n)のときに停止します。
したがって、複雑さはO(n^3log(n))
言語タグplsですか？ –
@Peet:' for 1 < - 1'またはそれ以外は何か？ – coderredoc
これはあなたの質問から明らかではないと思います。再帰的表記の権利を使用して時間の複雑さを記述する必要がありますか？私は言語が直感的な擬似コードだと思います。 – storaged