Complexidade computacional de algoritmos de cluster

Meu desejo é descrever a complexidade do tempo de várias abordagens de agrupamento. Por exemplo, suponha que tenhamos pontos de dados em m espaço dimensional.$n$$m$

Suponha-se ainda que a matriz de pares de dissimilaridade de n x n dimensões já é calculado e que já passou S ( m ⋅ n 2 ) passos. Qual é então a complexidade do tempo apenas de$\Delta$$n\times n$$O(m\cdot n^2)$

• cluster hierárquico (HC) usando a ligação de Ward
• HC usando ligação completa
• HC usando ligação média
• HC usando ligação única
• abordagem k- médio$k$
• abordagem k- significa$k$

Existe algum benefício se a matriz de dissimilaridade já não estiver computada? Pelo que entendi, é necessário para a abordagem HC e k -medóide, mas não para k - significa?$\Delta$$k$$k$

Obrigado pela ajuda!

O clustering de ligação única é quase o mesmo que o mínimo de árvores de abrangência em gráficos completos, fácil tempo O (n ^ 2). Para obter o tempo O (n ^ 2) para outros métodos de agrupamento aglomerado (incluindo certeza de ligação média e completa), consulte meu artigo "Agrupamento hierárquico rápido e outras aplicações de pares dinâmicos mais próximos", SODA '98 e JEA '00.

$k$$O(kn)$$k$$k$

$k$$k$