1 Свойства и структура алгоритма

Рассчитаем Θd,mcentroid для кластера, число элементов которого равно m
Θd,mcentroid = m⋅d сложений + d делений
Рассчитаем Θddistance в соответствие с формулой (2)
Θddistance = d вычитаний + d умножений + (d−1) сложение
Предположим, что алгоритм сошелся за i итераций, тогда временная сложность алгоритма Θd,nk−means
Θd,nk−means≤Θk,d,ninit+i(Θk,ddistribute+Θk,d,nrecenter)
Операции сложения/вычитания:
Θd,nk−means≤knd+i(kn(2d−1)+knd)=knd+i(kn(3d−1))∼O(ikdn)
Операции умножения/деления:
Θd,nk−means≤kd+i(knd+kd)=kd+ikd(n+1)∼O(ikdn)
Получаем, что временная сложность алгоритма k-means кластеризации n d-мерных векторов на k кластеров за i итераций:
Θd,nk−means∼O(ikdn)

1.7 Информационный граф

Рассмотрим информационный граф алгоритма. Алгоритм k-means начинается с этапа инициализации, после которого следуют итерации, на каждой из которых выполняется два последовательных шага (см. "Схема реализации последовательного алгоритма"):

• 
  распределение векторов по кластерам
  
• 
  перерасчет центров кластеров
  

Поскольку основная часть вычислений приходится на шаги итераций, распишем информационные графы данных шагов.
Распределение векторов по кластерам
Информационный граф шага распределения векторов по кластерам представлен на рисунке 1. Исходами данного графа является исходные векторы x1,...,xn, а также центры кластеров μ1,...μk, вычисленные ранее (на шаге инициализации, если рассматривается первая итерация алгоритма, или на шаге пересчета центров кластеров предыдущей итерации в противном случае). Каждая пара векторов данных xi, i=1,...,n, и центров кластера μj, j=1,...,k : (xi, μj) подаются на независимые узлы "d" вычисления расстояния между векторами (более подробная схема вычисления расстояния представлена далее, рисунок 2). Далее узлы вычисления расстояния "d", соответствующие одному и тому же исходному вектору xi передаются на один узел "m", где далее происходит вычисление новой метки кластера для каждого вектора xi (берется кластер с минимальным результатом вычисления расстояния). На выходе графа выдаются метки кластеров , L1,...,Ln, такие что ∀xi, i=1,...,n, xi∈Sj⇔Li=j.

Рис. 1. Схема распределения векторов по кластерам. d – вычисление расстояния между векторами; m – вычисление минимума.