Algoritmo e complexidade

Para efetuar o cálculo dessa medida de distância, propusemos o seguinte algoritmo:

Sendo que a diferença local é calculada através do seguinte algoritmo:

Pode-se mostrar que a complexide da instrução 1 do algoritmo DISTÂNCIAFUZZY é de $O(\vert T\vert^2)$ e a complexidade da instrução 2 é de $O(\vert T\vert) \cdot O($DIFERENÇALOCAL$)$. Em relação ao algoritmo DIFERENÇALOCAL, a complexidade do laço 1 e 2 é de $O(b^2)$. Assim, supondo que $\forall {\bf x} \in T$ o número de padrões nas bolas $B({\bf x}, \tau)$ é $b$ e a complexidade do algoritmo DISTÂNCIAFUZZY é de $O(\vert T\vert^2) + O(\vert T\vert) \cdot O(b^2)$.

Assim, no melhor caso (em termos de tempo de execução), se $\tau$ for tão pequeno que $B({\bf x}, \tau)$ contenha apenas ${\bf x}$, $\forall {\bf x} \in T$, a complexidade desse algoritmo será $O(\vert T\vert^2) + O(\vert T\vert) = O(\vert T\vert^2)$. No pior caso, se $\tau$ for tão grande que $B({\bf x}, \tau)$ contenha todos os padrões de $\forall {\bf x}_j \notin \omega_i$, a complexidade desse algoritmo será $O(\vert T\vert^2) + O(\vert T\vert) \cdot O(\vert T\vert^2) = O(\vert T\vert^3)$.