私は再発関係を持っています、それは次のようなものです：
T(e n ) = 2(T(en -1 )) + e n、ここで e は自然対数です。
これを解決して Θ 境界を見つけるために、次のことを試しました: k=e nを入力すると、方程式は次のように変換されます。
T(k)=2T(k/e)+k
次に、マスター定理を使用してみます。マスター定理によれば、a=2、b=e>2、f(k)=k です。したがって、いくつかの ε>0 に対して f(k)=Ω(n log b a+ε ) の場合があるため、T(k)=Θ(f(k))=Θ(k) となります。次に k=n とすると、T(n)=Θ(n) となります。私のソリューションに間違いはありますか？
この手順を 1 つずつ実行していきましょう。
あなたには再発があります
T(en ) = 2 T(en - 1 ) + e n
では、変数置換を行ってみましょう。k = e nを定義します。次に、取得します
T(k) = 2T(k / e) + k
この場合、マスター定理を使用すると、a = 2、b = e、および f(k) = k が得られます。logb a = ln 2 < 1 および f(k) = Θ(k) であるため、マスター定理によれば、再帰は S(k) = Θ(k) に解決されます。
ここで k = n' を設定すると (n' は関数への実際の入力)、T(n') = Θ(n) となり、完了です。はい、数学はチェックアウトします。
お役に立てれば！