および: f(x, y)_g(n)
def f(x, y):
if x < 1 or y < 1:
return 1
return f(x - 1, y - 1) + f(x - 1, y - 1)
def g(n):
return f(n, n)
のビッグシータ境界はg(n)何ですか?
x == y であるため、条件 inf(x, y)が真になることは決してないため、2 つの再帰呼び出しによって複雑さが決まると考えました。
のみを考慮f(x - 1, y - 1)すると、基本ケースに到達するにはn回の再帰呼び出しが必要であり、各呼び出しは別の呼び出しに分岐しf(x - 1, y - 1)ます。この時点で、私は続行する方法がわかりません。
(答えは Θ(2 n ) です。)