0

Catalan Numbersを計算する再帰関数を作成しました。再帰式はここに画像の説明を入力です。

私のコード:

def catalan(n): # We call this function. To my opinion it is more elegant.
    d = dict()
    return catalan_rec(n,d)

def catalan_rec(n,d):
    if n == 0:
        result = 1
    elif n in d: return d[n]
    else:
        result = 0
        for i in range(n):
            result += catalan_rec(i,d)*catalan_rec(n-i-1,d)
        d[n] = result
    return result

ここで、再帰の深さが O(n) であることは明らかです。このアルゴリズムの時間の複雑さはわかりません。再帰ツリーには O(n) 個のノードがあり、任意のノード (葉を除く) で 2 つの呼び出しを行います。辞書に結果が既にあるかどうかのみを確認するため、すべての呼び出しは O(1) です。したがって、時間の複雑さは O(n) です。

私の推論は正しいですか？

ところで、O(n^2) よりも優れた時間計算量で実行される非再帰アルゴリズムを作成するオプションはありますか?

ありがとう！

4

1 に答える 1

1

これがあなたが望むものかどうかはわかりませんが、そのページによれば、次のように O(n) でカタロニア語数を計算する関数を書くことができます:

def catalan(n):
    num, div = 1, 1
    for x in range(n + 2, 2*n + 1):
        num *= x
    for x in range(2, n + 1):
        div *= x
    return num / div
于 2015-08-27T05:56:59.967 に答える