algorithm - Theta(...) の特定のランタイムを持つ再帰関数

Question

私はアルゴリズムコースから得たこの宿題で立ち往生しています：

ランタイムが Theta(n^4 logn) の再帰関数を記述します。

私はこのようなことを考えましたが、私のアプローチについては非常に確信が持てません。

function(int n)
{
   for-loop (1..n^4)
     //do something

   return function(n/2);
}

score 1 · Accepted Answer

あなたの関数にはいくつかの問題があります:

マスター定理により、これは Θ(n^4) です。

ヒント: の係数を増やす必要がありますT(n/2)が、どれくらいですか? 自分で見つけてください。この増加のために、あなたはそれをx倍と呼ぶことができます。

マスター定理log nによると、次のような再帰がある場合に発生します。

T(n) = a T(n/b) + n ^a/b

あなたの場合、a/b = 4 があるので、これを達成するために b = 2 と a = 8 を修正できます。

T(n) = 8T(n/2) + n ⁴

これに到達するには、T(n/2) を 8 回呼び出すことができます。

score 0 · Accepted Answer

ヒント: n ⁴は、1 から n までの 4 つのネストされたループである可能性があります。対数ランタイム係数は、通常、問題のサイズを 1 に達するまで再帰的に半分にすることによって得られます。

func(int n)
  for i = 1 to n^4 log n
     nop()

しかし、これが探し求められているものだとは思いません。

score -1 · Accepted Answer

あなたのアプローチは正気であり、あなたの不安は正常です。アルゴリズムが Theta(n^4 log n) であることを証明する必要があります。通常のアルゴリズム分析手法を適用して、n^4 log_2 n 回function実行することを示します。do something

ヒント: 再帰的に呼び出された回数functionと、各呼び出しでループが実行される頻度を数えます。関数にはまだ小さなバグがあることがわかります。因子のはn、再帰呼び出しごとに削減されます。n^4

3 に答える 3