Какова временная и пространственная сложность алгоритма FP-Growth?

Question

Как рассчитать временную сложность и пространственную сложность алгоритма FP_growth в Data Mining ??

Answer 1

Для сложности, вы можете найти часть ответа в этой статье: «Анализ сложности» Depth First и FP-Growth реализации APRIORI "(http://www.liacs.nl/~kosters/complap.ps) (настоящий документ в формате постскриптума)

Answer 2

Согласно моему пониманию, временная сложность должна быть O (n ² ), если количество уникальных элементов в наборе данных равно n.Сложность зависит от поиска путей в дереве FP для каждого элемента таблицы заголовков, который зависит от глубины дерева.Максимальная глубина дерева ограничена сверху n для каждого из условных деревьев.Таким образом, порядок: O (количество элементов в таблице заголовков * максимальная глубина дерева) = O (n * n).