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

Пересчет центров кластеров
Для этого шага алгоритма производится пересчет центров кластера по формуле вычисления центра масс:

μ=1|S|∑x∈Sx

(3)

1.5 Схема реализации последовательного алгоритма

1. Инициализировать центры кластеров μ(1)i, i=1,...,k
2. t←1
3. Распределение по кластерам
S(t)i={xp:∥xp−μ(t)i∥2≤∥xp−μ(t)j∥2∀j=1,...,k},
где каждый вектор xp соотносится единственному кластеру S(t)
4. Обновление центров кластеров
μ(t+1)i=1|S(t)i|∑xj∈S(t)ixj
5. if ∃i∈1,k¯¯¯¯¯¯¯:μ(t+1)i≠μ(t)i then
t=t+1;
goto 3;
else
stop

1.6 Последовательная сложность алгоритма

Обозначим Θd,mcentroid временную сложность вычисления центорида кластера, число элементов которого равна m, в d-мерном пространстве.
Аналогично Θddistance – временная сложность вычисления расстояния между двумя d-мерными векторами.
Сложность шага инициализации k кластеров мощности m в d-мерном пространстве – Θk,d,minit

• 
  Стратерия Forgy: вычисления не требуются, Θk,d,minit=0
  
• 
  Стратегия случайного разбиения: вычисление центров k кластеров, Θk,d,minit=k⋅Θd,mcentroid,m≤n
  

Cложность шага распределения d мерных векторов по k кластерам – Θk,ddistribute
На этом шаге для каждого вектора xi∈X, i=1,...,n, вычисляется k расстояний до центров кластеров μ1,...μk
Θk,ddistribute=n⋅k⋅Θddistance
Сложность шага пересчета центров k кластеров размера m в d-мерном пространстве – Θk,d,mrecenter
На этом шаге вычисляется k центров кластеров μ1,...μk
Θk,d,mrecenter=k⋅Θd,mcentroid