algorithm - FP-Growth アルゴリズムの時間と空間の複雑さは?

Question

データ マイニングの FP_growth アルゴリズムの時間の複雑さと空間の複雑さをどのように計算しますか??

Answer 1

複雑さについては、この論文で答えの一部を見つけることができます: " Complexity Analysis of Depth First and FP-growth Implementations of APRIORI " (この論文は postcript 形式です)

Answer 2

私の理解によれば、データセット内の一意のアイテムの数が n の場合、時間計算量は O(n ² )になるはずです。複雑さは、ヘッダー テーブルの各要素の FP ツリー内のパスの検索に依存します。これは、ツリーの深さに依存します。ツリーの最大深さは、条件付きツリーごとに n の上限があります。したがって、順序は次のとおりです。O (ヘッダー テーブルの項目数 * ツリーの最大深さ) = O(n*n)。