面白いと思いますが、解決策がわかりません。このアルゴリズムは x nを計算します
マスター定理を使用すると、私の推論は次のようになります
T(n) = 2 T(n/2) + f(n)
しかし、この場合の f(n) は 1 ですか? n <= 4 は定数であるためです。私に与えます：
T(n) = Θ(n)
置換を使用すると、この答えが得られます
T(n) = Θ(n + log(n))
私は多くのことを間違っていると思います。誰かが私を正しい方向に向けることができますか?
T(n) = Θ(n + log(n)) は単に T(n) = Θ(n) です。theta を使用する場合は、下位項 (log(n)) を省略できます。
また、再帰ごとに 1 つの乗算 (rek(x, n/2) * rek(x, (n + 1)/2)) しか行っていないため、f(n) は O(1) です。
複雑さは0（n）です。説明：単純なサイクルを使用する場合と同様に、すべての乗算を行います。また、*の数で割った数がconstよりも大きい操作はありません。したがって、複雑さは、0（n）を作成するconst * 0（n）についてです。